分析

这题构造一下链和菊花的情况会理解地更透彻一些。

“三步走”战略啊不，距离为 3 的点，它们所在的深度肯定是不同的。也就是说，我们能把整棵树按照节点深度奇偶性黑白染色，分成两个集合，距离为 3 的点一定在不同的集合里。

对于 \((i,j)\)，要求 \(p_i \cdot p_j \equiv 0 \; (\bmod 3)\) 或者 \(p_i + p_j \equiv 0 \; (\bmod 3)\)，又可以按照节点编号模 3 的结果来分成 3 个集合。其中模三为 0 的那个集合是最特殊的，因为其中的任意一个点和其他所有点组成的点对都是合法的。

为了方便，称 n 类点 表示模 3 为 n 的点。

很容易知道 0 类点的个数为 \(\lfloor \frac{n}{3}\rfloor\)，接下来就是大胆构造，绝不证明。

如果黑白某个集合节点个数小于等于 \(\lfloor \frac{n}{3}\rfloor\)，那么如果把所有的 0 类点放到这个集合里，另一个集合无论怎么选，都是一组合法解，因为乘积均为 3 的倍数。

但是如果每个集合都大于 \(\lfloor \frac{n}{3}\rfloor\) 呢？

注意到 1 类点和 2 类点，它们的和模 3 为 0，即 3 的倍数。所以一个集合全放 1 类点，一个集合全放 2 类点，0 类点随便放——因为它们和任何点组成的点对都是合法的。

实现还是 STL 好用。

CODE

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
const int N=2e5+10;
#define pb push_back
int n, col[N], p[N];
vector<int> g[N], c[2], v[3];
// c存节点黑白染色，v存模3
void dfs(int x,int fr) {
    col[x]=col[fr]^1, c[col[x]].pb(x);
    // 按照深度奇偶黑白染色
    for(auto y:g[x]) if(y!=fr) dfs(y,x);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) v[i%3].pb(i);
    for(int i=1;i<n;++i) {
        int x, y; scanf("%d%d",&x,&y);
        g[x].pb(y), g[y].pb(x);
    }
    dfs(1,0);
    if(c[0].size()<c[1].size()) swap(c[0],c[1]);
    // 取较小的集合
    if(c[1].size()<=n/3) {
        for(auto cc:c[1]) p[cc]=v[0].back(), v[0].pop_back();
        // 全放0类点
        for(auto cc:c[0])
        	if(v[1].size()) p[cc]=v[1].back(), v[1].pop_back();
        	else if(v[2].size()) p[cc]=v[2].back(), v[2].pop_back();
        	else p[cc]=v[0].back(), v[0].pop_back();
        // 随便放
    } else {
        for(auto cc:c[1])
            if(v[1].size()) p[cc]=v[1].back(), v[1].pop_back();
            else if(v[0].size()) p[cc]=v[0].back(), v[0].pop_back();
        // 分别放1类点和0类点，不足用0类点补齐
        for(auto cc:c[0])
        	if(v[2].size()) p[cc]=v[2].back(), v[2].pop_back();
        	else if(v[0].size()) p[cc]=v[0].back(), v[0].pop_back();
    }
    
    for(int i=1;i<=n;++i) printf("%d ",p[i]);
}