题目描述
给一棵树,点数 1-n,所有的边一开始是没有权重的。现在需要给树分配权重,使树上没有分配权重前,任意距离不超过2的两个点在分配权重后的距离为质数。
题解
其实是个思维题。距离为1肯定不超过2,所以所有边都应该是质数。
而如果对相邻的两条边都分配奇数,两个奇质数的和一定是偶数,是绝对不可以的。那么我们只能给两条相邻的边分配2和一个合适的奇质数(比如3或5这样,自身加上2还是质数的)。
那么实际上只有一条链的情况才能满足题目要求,因为如果某个点度数大于2,则至少为3,根据抽屉原理,一定有2个2或2个奇数,这两种情况都是不满足要求的。
之后就是快乐的二染色了。
/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2022-03-17
*
* @copyright Copyright (c) 2022
*
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int t, n, d[maxn], w[maxn], vis[maxn], nums[maxn];
struct edge{
int to, index;
};
vector<edge> edges[maxn];
vector<int> begins;
void clearcontext(){
for (int i = 1; i <= n; i++)
edges[i].clear();
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));
begins.clear();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--){
cin >> n;
for (int i = 1; i < n; i++){
int fm, to;
cin >> fm >> to;
edges[fm].push_back({to, i}), edges[to].push_back({fm, i});
d[fm]++, d[to]++;
}
int flag = 1;
for (int i = 1; i <= n; i++){
if(d[i] >= 3){
flag = -1;
}
if(d[i] == 1){
begins.push_back(i);
}
}
if(flag == -1){
cout << -1 << endl;
clearcontext();
continue;
}
else{
queue<int> q;
q.push(begins[0]), vis[begins[0]] = 1, nums[begins[0]] = 1;
while(!q.empty()){
int now = q.front();
vis[now] = 1;
for(auto &iter : edges[now]){
int nto = iter.to;
if(!vis[nto]){
w[iter.index] = (!nums[now] ? 2 : 3);
nums[nto] = !nums[now];
q.push(nto);
}
}
q.pop();
}
for (int i = 1; i < n; i++){
cout << w[i] << " ";
}
cout << endl;
}
clearcontext();
}
return 0;
}