AT5759

Aryper · 2021-08-25 13:23:30 · 个人记录

ThREE

构造题。

黑白染色整棵树。

如果说某种颜色的点 \le \lfloor\frac{n}{3}\rfloor，将全部该种颜色的点赋上 3 的倍数的权值，另一种颜色随便填。

否则，我们把与 1 同余的权值全部赋到某个颜色的点里，这个颜色的剩余的点赋上 3 的倍数的权值。与 2 同余的权值则全部赋到另一个颜色的点了，这个颜色的剩余的点也赋上 3 的倍数的权值。

时间复杂度 O(n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=2e5;

ll n,u,v,tot;

ll dt[N+5],col[3],cnt[2],ans[N+5];

ll ver[N*2+5],nxt[N*2+5],head[N+5];

void dfs(ll p,ll fath) {
    dt[p]=dt[fath]+1;cnt[dt[p]%2]++;
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==fath) continue;
        dfs(ver[i],p);
    }
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();col[n%3]++;

    for(ll i=1;i<n;i++) {
        u=read();v=read();
        add(u,v);add(v,u);
        col[i%3]++;
    }

    dfs(1,0);

    if(cnt[0]<=n/3||cnt[1]<=n/3) {
        for(ll i=1;i<=n;i++) {
            if(cnt[dt[i]%2]>n/3) {
                if(col[1]) ans[i]=(col[1]-1)*3+1,col[1]--; 
                else
                if(col[2]) ans[i]=(col[2]-1)*3+2,col[2]--;
                else ans[i]=col[0]*3,col[0]--;
            }
            else {
                ans[i]=col[0]*3,col[0]--;
            }
        }
        for(ll i=1;i<=n;i++) {
            write(ans[i]);putchar(' ');
        }
    }
    else {
        for(ll i=1;i<=n;i++) {
            if(col[dt[i]%2+1]) ans[i]=(col[dt[i]%2+1]-1)*3+dt[i]%2+1,col[dt[i]%2+1]--;
            else ans[i]=col[0]*3,col[0]--;
        }
        for(ll i=1;i<=n;i++) {
            write(ans[i]);putchar(' ');
        }
    }

    putchar('\n');

    return 0;
}