题目传送门：P9498 「RiOI-2」equals - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这是洛谷月赛Div.2 T3 ，由于我比较菜，只能赛场上切到T3（T4是黑。)，开题我们很容易就看出这道题首先需要初始化每个点到根节点的最短路，而且边权都为1，所以我们先无脑打一个堆优化的dijkstra，剩下的就是处理方案了，我们可以先求出每个距离点的个数和点的距离和，如果这个和是奇数，我们直接输出-1就可以溜了，如果是偶数，那么我们就要求一下方案，我们可以设置两个变量，sum1&sum2，将点的距离累加在这两个变量上（如果sum1>sum2则加sum2，反之加sum1)，在过程中记录方案，最后看它们是否相等。但这时会出现一个问题，如果我们乱序枚举，很可能出现本身能用一个大数弥补的差距我们用了很多小数，导致差距很小，最后又给了一个大数，那么sum1和sum2可能本身有可能相等，但由于我们的策略导致枚举结束后不相等。根据我们吃自助餐的经验(bushi)，我们肯定要先吃硬菜主食，最后再喝饮料填缝，同理，我们也要先取距离大的点，再用距离小的点弥补两点间的差距，当然也有可能和是偶数然而并不能平均染色的情况，所以我们最后在判断一下（事实证明不加这个特判也可以过)，最后输出方案即可
警钟长鸣：long long !!!!!!!
代码如下：
#include<bits/stdc++.h> using namespace std; const int N = 5000005; int n,m; int hd[N],ver[N],nxt[N],dis[N],mk[N]; int r[N]; int idx,s; long long sum[N],sum1,sum2; long long qsum; struct node{ int idx,v; }; priority_queue <node> q; bool operator < (const node &x,const node &y){ return x.v > y.v; } void add(int x,int y){ ver[++idx] = y; nxt[idx] = hd[x]; hd[x] = idx; } void dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1] = 1; q.push((node){1,1}); while(q.size()){ node t = q.top(); q.pop(); if(mk[t.idx]) continue; mk[t.idx] = 1; for(int i = hd[t.idx];i;i = nxt[i]){ int y = ver[i]; if(!mk[y]&&dis[y] > dis[t.idx]+1){ dis[y] = dis[t.idx]+1; q.push((node){y,dis[y]}); } } } } int main(){ scanf("%d",&n); int f = 0; for(int i = 1;i < n;i++){ int x,y; scanf("%d%d",&x,&y); if(x == y) continue; add(x,y); add(y,x); } s = 1; dijkstra(); int mx = 0; for(int i = 1;i <= n;i++){ sum[dis[i]]++; mx = max(dis[i],mx); } for(int i = 0;i <= mx;i++){ qsum+=sum[i]*i; } if(qsum%2){ printf("-1"); return 0; } for(int i = mx;i > 0;i--){ while(sum[i]){ if(sum1 < sum2){ sum1+=i; sum[i]--; r[i]++; }else{ sum2+=i; sum[i]--; } } } if(sum1!=sum2){ printf("-1"); return 0; } for(int i = 1;i <= n;i++){ if(r[dis[i]]){ printf("1 "); r[dis[i]]--; }else printf("0 "); } return 0; }