遇树必去世，上次cf，昨晚训练赛，今晚训练赛，要好好补补了~
Coloring Edges on Tree
时间限制: 1 Sec 内存限制: 128 MB Special Judge
[提交] [状态]
题目描述
Given is a tree G with N vertices. The vertices are numbered 1 through N, and the i-th edge connects Vertex ai and Vertex bi.
Consider painting the edges in G with some number of colors. We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.
Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.
Constraints
·2≤N≤105
·1≤ai<bi≤N
·All values in input are integers.
·The given graph is a tree.
输入
Input is given from Standard Input in the following format:
N
a1 b1
a2 b2
⋮
aN−1 bN−1
输出
Print N lines.
The first line should contain K, the number of colors used.
The (i+1)-th line (1≤i≤N−1) should contain ci, the integer representing the color of the i-th edge, where 1≤ci≤K must hold.
If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.
样例输入 Copy
【样例1】
3
1 2
2 3
【样例2】
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8
【样例3】
6
1 2
1 3
1 4
1 5
1 6
样例输出 Copy
【样例1】
2
1
2
【样例2】
4
1
2
3
4
1
1
2
【样例3】
5
1
2
3
4
5
题意： 给定一个n个节点的树，要求染色时相邻边的颜色不相同，要求输出一种所需的总颜色数最小的方案。
思路：
具体的证明可以看这里：传送门
大体思路就是选择一个度数最多的点作为起点开始染色，保证每个点所连接的边的颜色都不相同。
这简直是那天cf题目的变式（可能是我对树不敏感~）
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=1e6+7; struct node{ int c,a,b; }a[maxn]; int h[maxn],s[maxn],idx,maxx=-1; int n,root; void add(int x,int y,int z){ a[idx].c=z;a[idx].a=y;a[idx].b=h[x];h[x]=idx++; } int c[maxn];//涂色的数组 int cnt[maxn]; void dfs(int u,int fa,int pre){ int x=1; if(x==pre) x++;///不能与上一个同色 if(x>maxx) x=1;///最多用maxx种颜色 for(int i=h[u];~i;i=a[i].b){///将该节点进行染色 int v=a[i].a,num=a[i].c; if(c[num]||v==fa) continue; c[num]=x; x++; if(x>maxx) x=1; if(x==pre) x++; if(x>maxx) x=1; } for(int i=h[u];~i;i=a[i].b){ int v=a[i].a,num=a[i].c; if(v!=fa) dfs(v,u,c[num]); } } int main(){ memset(h,-1,sizeof h); n=read(); for(int i=0;i<n-1;i++){ int x,y; x=read();y=read(); add(x,y,i);add(y,x,i); cnt[x]++,cnt[y]++; } for(int i=1;i<n;i++)///找度数最大的节点 if(cnt[i]>maxx){ maxx=cnt[i]; root=i; } printf("%d\n",maxx); dfs(root,0,0);///从根节点开始染色 for(int i=0;i<n-1;i++) printf("%d\n",c[i]); return 0; }
