C

题目：传送门

题意：有一颗 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;
}