【树上染色】ABC146 D

灰太狼 2024-03-16 14:41 57阅读 0赞

[D - Coloring Edges on Tree (atcoder.jp)][D - Coloring Edges on Tree _atcoder.jp]

题意：

给定一棵树，让你给这棵树的边染色，使得对于一个结点，与其相邻的所有边的颜色都不一样，要求颜色种数要最少

![481fb46a92e84b68bdd10118a39d28c0.png][]

思路：

树上染色

分为给点染色或者给边染色

一般树上染色问题是周期性的染色，那么颜色就是(++idx)%T

染色的时候dfs要加参数col

如果是给点染色，这个col代表的是给该点染成col

如果是给边染色，这个col代表的就是该点u到其父节点的边的颜色，给边染色需要给边加一个属性id，方便记录答案

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    
    struct ty{
    	int to,next,id;
    }edge[mxe<<2];
    
    int N,u,v;
    int tot=0;
    int head[mxn],a[mxn];
    
    void add(int u,int v,int id){
    	edge[tot].id=id;
    	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,int col){
    	int c=1;
    	for(int i=head[u];~i;i=edge[i].next){
    		if(edge[i].to==fa) continue;
    		if(c==col) c++;
    		a[edge[i].id]=c;
    		dfs(edge[i].to,u,c);
    		c++;
    	}
    }
    void solve(){
    	cin>>N;
    	G_init();
    	for(int i=1;i<=N-1;i++){
    		cin>>u>>v;
    		add(u,v,i);
    		add(v,u,i);
    	}
    	dfs(1,-1,-1);
    	cout<<*max_element(a+1,a+1+N-1)<<'\n';
    	for(int i=1;i<=N-1;i++) cout<<a[i]<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[D - Coloring Edges on Tree _atcoder.jp]: https://atcoder.jp/contests/abc146/tasks/abc146_d
[481fb46a92e84b68bdd10118a39d28c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3fe928ed8e67439da992166d3c3da253.png