【树上染色】ABC303E

拼搏现实的明天。 2024-03-16 07:40 96阅读 0赞

**树上染色就是树上有规律地编号！(确信**

[E - A Gift From the Stars (atcoder.jp)][E - A Gift From the Stars _atcoder.jp]

题意：

![a0b1c928f9e747d98193af2db0e7e059.png][]

![cddbb0b864344bcfb80b600d407fe2d2.png][]

![616ceedaaeee4164a7915c01aeff3655.png][]

![efa84c32fbcf4fe5902420ea5e51085f.png][]

思路：

若干菊花图连在一起，每个菊花图的中心之间的距离都是2

因此我们可以给这棵由菊花图构成的树编号，即进行染色

然后DFS统计即可

![7f8cb5349ff4423e9b5121a19b041c96.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    vector<int> V;
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    int N;
    int u,v,tot=0;
    int head[mxn],in[mxn],col[mxn];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void dfs1(int u,int fa,int c){
        col[u]=c;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs1(edge[i].to,u,(c+1)%3);
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
            in[u]++;
            in[v]++;
        }
        int pos1,pos2;
        for(int i=1;i<=N;i++){
            if(in[i]==1){
                pos1=i;
                break;
            }
        }
        dfs1(pos1,0,0);
        for(int i=1;i<=N;i++){
            if(col[i]==1) V.push_back(in[i]);
        }
        sort(V.begin(),V.end());
        for(int i=0;i<V.size();i++) cout<<V[i]<<" \n"[i==V.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[E - A Gift From the Stars _atcoder.jp]: https://atcoder.jp/contests/abc303/tasks/abc303_e
[a0b1c928f9e747d98193af2db0e7e059.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ba8e8e7a635c465485c5e04d2f17ffe1.png
[cddbb0b864344bcfb80b600d407fe2d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/c6b24abcb8354f538fd92097ff49639f.png
[616ceedaaeee4164a7915c01aeff3655.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/c372f09510af4dbd9ccee05a4d69811c.png
[efa84c32fbcf4fe5902420ea5e51085f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/99dbb455d5f0423c8f222f46974f93af.png
[7f8cb5349ff4423e9b5121a19b041c96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/01fbf5eea4bd498fb8205d54329ff1d6.png