CF1627 C.Not Assigning【思维】

题目链接：codeforces 1627C

题解

给一颗树的边赋值，单条边的权值为质数，相邻两条边的权值和也为质数。

不难发现必然有一条边的权值是 ，与这条边相邻的边的权值是其他任意质数。所以，显然，如果存在可行解的的话，这颗树已经退化成一条链，即不可能有一个节点的度为 。

于是，只要找到这条链的一端，然后再去根据条件赋值即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
void solver(){
    int n;
    cin >> n;
    vector<array<int, 2>> a[n+1];
    for (int i = 1; i <= n-1; i++) {
        int u, v;	cin >> u >> v;
        a[u].push_back({v, i});
        a[v].push_back({u, i});
    }
    bool flag = 1;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        flag &= (a[i].size() <= 2);
        cur = (a[i].size() == 1? i : cur);
    }
    if (flag) {
        vector<bool> vis(n+1, 0);
        vector<int> ans(n+1, 0);
        int w = 2;
        while (!vis[cur]) {
            vis[cur] = true;
            for (auto [v, id] : a[cur]) {
                if (!vis[v]) {
                    ans[id] = w;
                    w ^= 1;
					cur = v;
                    break;
                }
            }
        }
        for (int i = 1; i <= n-1; i++) cout << ans[i] << " \n"[i == n];
    } else cout << -1 << endl;
}
int main() {
    int _ = 1;
    cin >> _;
    while (_--) {
        solver();
    }
    return 0;
}