【Tree树上染色+贪心】CF1387B1

柔光的暖阳◎ 2024-03-16 07:40 62阅读 0赞

[Problem - 1387B1 - Codeforces][]

题意：

![946309f0da624ae09c2715a343db0b1d.png][]

![0a3fea1a218b435aa4913dc4be7cc387.png][]

思路：

观察样例可知

当N为偶数时，其实就是相邻两个点交换

当N为奇数时，对于多出来的三个点，三个之间交换即可

事实上就是这么做的，但是看起来比较难写

但其实也不难写，只需要树上染色然后维护答案就行了

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 dfs(int u,int fa){
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
            if(!col[u]&&!col[edge[i].to]){
                col[u]=edge[i].to;
                col[edge[i].to]=u;
            }
        }
    }
    void solve(){
        cin>>N;
        G_init();
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        int ans=0;
        for(int u=1;u<=N;u++){
            if(col[u]){
                ans++;
                continue;
            }
            int v=edge[head[u]].to;
            col[u]=col[v];
            col[v]=u;
            ans+=2;
        }
        cout<<ans<<'\n';
        for(int i=1;i<=N;i++) cout<<col[i]<<" \n"[i==N];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - 1387B1 - Codeforces]: https://codeforces.com/problemset/problem/1387/B1
[946309f0da624ae09c2715a343db0b1d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/a654aff0d05b489684d2b0379c27e66e.png
[0a3fea1a218b435aa4913dc4be7cc387.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/b5a2db3eaaec432db1c929b1221744a4.png