题目：传送门
题意：有一颗 n 个节点的树，有 n - 1 条边，然后现在需要你构造一个排列 p1,p2,p3......,pn 满足对于任意的 (i, j) 如果节点 i 到节点 j 的最短距离等于 3 ，那么 pi * pj 是 3 的倍数或者 pi + pj 是 3 的倍数.
2 <= n <= 2e5
思路：
这题可以直接忽略掉节点 i 到节点 j 的最短距离等于 3 这个条件.
我们可以对每个节点染色，如果节点 i 到节点 1 的距离为偶数，那么颜色为 0.
如果节点 i 到节点 1 的距离为奇数，那么颜色为 1.
这样的话，距离为 3 的两个节点肯定颜色是不一样的。
接下来考虑，是否能构造一个序列使得，任意颜色不同的两个节点都能满足 pi * pj 是 3 的倍数或者 pi + pj 是 3 的倍数.
那我们可以对 1 ~ n 分三组，分别是 %3 = 0, %3 = 1, %3 = 2. 我们假设 n % 3 == 0，难么每一组里面的元素个数就都是 n / 3
那我们对所有节点分成了两组，颜色为 0 和颜色为 1，那么我们假设颜色为 0 的节点个数大于颜色为 1 的节点个数.
我们设颜色为 0 的节点个数为 cnt. 那么 cnt 肯定大于等于 n / 2.
那么就有两种情况：
1、 cnt < n * 2 / 3
这种情况，我们可以把 %3 = 1 的放 n / 3 颜色为 0 的，把 %3 = 2 的放 n / 3 颜色为 1 的，然后剩下的不管是颜色为 0 或者颜色为 1 的都放在 %3 = 0 里面，这样是完全满足条件的。
2、n * 2 / 3 <= cnt <= n
这种情况，直接把 %3 = 1 和 %3 = 2 的都放颜色为 0 的，然后剩下的全部放在 %3 = 0 的，这样也可以满足条件。
所以无论如何，都是可以构造出满足条件的序列的。
#include <bits/stdc++.h> #define LL long long #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF INT_MAX #define inf LLONG_MAX #define PI acos(-1) #define fir first #define sec second using namespace std; const int N = 2e5 + 5; int ans[N]; vector < int > G[N]; vector < int > Q[2]; vector < int > P[3]; void dfs(int u, int fa, int op) { Q[op].pb(u); for(auto v : G[u]) { if(v == fa) continue; dfs(v, u, op ^ 1); } } void add(int op1, int op2) { while(!Q[op1].empty() && !P[op2].empty()) { ans[Q[op1].back()] = P[op2].back(); Q[op1].pop_back(); P[op2].pop_back(); } } void solve() { int n; scanf("%d", &n); rep(i, 1, n) P[i % 3].pb(i); rep(i, 1, n - 1) { int u, v; scanf("%d %d", &u, &v); G[u].pb(v); G[v].pb(u); } dfs(1, 0, 0); if(Q[0].size() > Q[1].size()) add(0, 1); else add(1, 1); if(Q[0].size() > Q[1].size()) add(0, 2); else add(1, 2); add(0, 0); add(1, 0); rep(i, 1, n) printf("%d ", ans[i]); puts(""); } int main() { // int _; scanf("%d", &_); // while(_--) solve(); solve(); return 0; }