Problem - 1627C - Codeforces

 题意：

一个n个节点的数， 给出 n-1 条边， 要求给每一条边赋值，使其满足：任意一条边或相连的两条边之和都是质数

题解：

这种情况，只有2和其它质数相加也是质数，这种题还是比较多， 能较容易想到。其次，题目没说所用的数不能重复， 索性只用2 3好了。 2333

接下来就是遍历树了，题目也没有说遍历头一定是1哦，最近好喜欢用map ^-^ , 好久没做链表加dfs来看路了， 竟然卡了

上代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N = 2e5+10;

int ne[N], h[N], e[N], idx=0;
int n, num[N],res[N];
bool st[N];
map<PII, int> mp;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a],h[a]=idx++; 
}  

void dfs(int x, int nn)
{
    
    st[x] = 1;
    for(int i = h[x]; i!=-1; i = ne[i])
    {
        if(!st[e[i]])
        mp[{x,e[i]}]=nn, dfs(e[i], 5-nn);
    }
    
}
int main()
{
    int t;
    cin >> t;
    
    while(t --)
    {
        memset(h, -1, sizeof h);
        memset(num, 0, sizeof num);
        memset(st, 0, sizeof st);
        mp.clear();
        vector<PII> ve;
        
        cin >> n;
        bool f=0;
        for(int i = 1; i < n; i ++)
        {
            int a, b;
            cin >> a >> b;
            if(a>b)swap(a,b);
            add(a, b);
            add(b, a);
            ve.push_back({a,b});
            ve.push_back({b,a});
            num[a]++; num[b]++;
            if(num[a]>2 || num[b]>2)f=1;
        }
        if(f)
        {
            puts("-1");
            continue;
        }
        
        for(int i=1;i<=n;i++)
            if(num[i]==1) 
            {
                dfs(i,2);            
                break;
            }
        for(int i =0; i < ve.size(); i ++)
            if(mp[ve[i]])
            cout << mp[ve[i]]<<' ';
        cout<<'\n';
    }
        return 0;
}