https://atcoder.jp/contests/hitachi2020/tasks/hitachi2020_c
某人很无聊，想给树上N个节点的每一个节点填一个1~N中的一个数。满足
$2\leqslant N\leqslant 2\times 10^5$
其实我不会，这是个构造题……
记一下之前的思路：
树上的点可以用距离为3的倍数这个等价关系分成3个商集 然后对3个树涂色，然后一顿乱涂，发现规约到NPC问题上去了……
把数字按照mod 3分成3类：A，B，C
相邻两个节点的颜色可以是A-B，A-C，B-C，C-C
C可以用来代替A或B，那么用A涂白色，B涂黑色，多余的部分用C涂
有个例外：$A+C$还不够涂白色，这时$B$肯定大于黑色的数量，因为A，B，C相差不超过1，因此等价于C大于等于黑色，用C涂黑色，剩下的随便涂
总结一下：
如果C大于等于黑色，那么用C涂黑色，剩下的随便涂
如果C大于等于白色，那么用C涂白色，剩下的随便涂
否则这时候A小于等于白色，B小于等于黑色，A涂白色，B涂黑色，不够的用C涂
这样就解决了1棵树的相邻节点的问题，距离为3可以拆成3个树，然后就解不出来了……
其实仍然可以用相邻节点，距离为3肯定保证不会出现A-A或B-B，这样就保证一定能构造出来
\[\begin{pmatrix}0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\end{pmatrix}^3=\begin{pmatrix}0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\end{pmatrix} \]
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define REP(i,a,b) for(register int i=(a); i<(b); i++)
#define REPE(i,a,b) for(register int i=(a); i<=(b); i++)
#define PERE(i,a,b) for(register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
#define MAXN 200007
int hd[MAXN<<1], nxt[MAXN<<1], to[MAXN<<1], m=0;
inline void adde(int a, int b) {
nxt[m]=hd[a]; hd[a]=m; to[m]=b; m++;
}
int q[MAXN], c[MAXN], ans[MAXN], vis[MAXN];
int use[3]={1,2,3};
int n;
int go(int v) {
if(use[v]>n) {
int r=use[2];
use[2]+=3;
return r;
}
int r=use[v];
use[v]+=3;
return r;
}
inline void bfs1() {
int f=0, r=0;
memset(vis,0,sizeof vis);
ans[0]=0, ans[1]=0;
q[f++]=1; c[1]=0; vis[1]=1; ans[0]++;
while(r<f) {
int n=q[r], s=c[n]^1; r++;
for(int i=hd[n]; ~i; i=nxt[i]) {
int t=to[i];
if(!vis[t]) {
vis[t]=1;
c[t]=s;
ans[s]++;
q[f++]=t;
}
}
}
}
int main() {
memset(hd,-1,sizeof hd);
scanf("%d", &n);
REP(i,0,n) {
int a,b; scanf("%d%d", &a, &b);
adde(a,b); adde(b,a);
}
bfs1();
if(ans[0]<=n/3) {
int now=1, c2=3;
REPE(i,1,n) {
if(c[i]==0) {ans[i]=c2;c2+=3;}
}
REPE(i,1,n) {
if(c[i]==1) {
if(now%3==0 && now<c2) now++;
ans[i]=now;
now++;
}
}
} else if(ans[1]<=n/3) {
int now=1, c2=3;
REPE(i,1,n) {
if(c[i]==1) {ans[i]=c2;c2+=3;}
}
REPE(i,1,n) {
if(c[i]==0) {
if(now%3==0 && now<c2) now++;
ans[i]=now;
now++;
}
}
} else {
REPE(i,1,n) {
ans[i]=go(c[i]);
}
}
REPE(i,1,n) { if(i>1)putchar(‘ ‘);
printf("%d", ans[i]);
}
}
原文：https://www.cnblogs.com/sahdsg/p/12450101.html