题目大意： 给你一个不超过20万个点树，要求给每条边染色，要求最多不能有超过k个点他们的边染了相同的颜色。 求最少需要多少颜色和具体方案。

 

 

 

思路： 树上边的染色问题，其实很容易， 如果没有k的限制，所有点里面最大的度数就是我们的答案。  现在有k的限制，我们只要度排名在n-k的点的度是多少就我们的答案。 注意是度从小到大排序。 

 

然后我们dfs依次构造染色方案，非常的容易，只要当前的颜色和之前的颜色不一样就可以了，可以循环染色，即使用%

 

1 #include
      
        2 using namespace std;   3 #define R register int   4 #define rep(i,a,b) for(R i=a;i<=b;i++)  5 #define Rep(i,a,b) for(R i=a;i>=b;i--)  6 #define gc()       getchar()   7 #define ms(i,a)    memset(a,i,sizeof(a))  8 template
       
        void read(T &x){ 9     x=0; char c=0;  10     while (!isdigit(c)) c=gc();  11     while (isdigit(c)) x=x*10+(c^48),c=gc();  12 }13 int const N=200000+3;  14 struct Edge{15     int to,nt,id;  16 }e[N<<1];  17 int n,k,d[N],cnt,h[N],col[N];  18 void add(int a,int b,int c){19     e[++cnt]=(Edge){b,h[a],c}; h[a]=cnt;  20 }21 void dfs(int x,int fa,int c){22     for(R i=h[x]; i; i=e[i].nt){23         int v=e[i].to;  24         if(v==fa) continue;  25         c=(c+1)%d[n-k];  26         col[e[i].id]=c;  27         dfs(v,x,c);   28     }29 } 30 int main(){31     read(n); read(k); 32     rep(i,1,n-1){33         int x,y; read(x); read(y); 34         add(x,y,i);  35         add(y,x,i);  36         d[x]++;d[y]++;  37     }38     sort(d+1,d+n+1);  39     printf("%d\n",d[n-k]);  40     dfs(1,-1,-1);  41     rep(i,1,n-1) printf("%d ",col[i]+1);  42     return 0 ;43 }44     45     46