Privatization of Roads in Treeland （贪心+染色）

思路： 

• 重点是染色，不用先把贪心的点拉出来染色（这样之后不好染其他的点）
• 直接谁便一个点开始DFS染色，遇到贪心的点特判一下就OK了。

题目：SWJTU—春季集训 - Virtual Judge (vjudge.net) 

#include 
using namespace std;
#define ri register int
#define M 400015

template <class G> void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=ch=='-';ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}
 
int n,m;
int head[M],to[M],nxt[M],co[M];
int cent=1;
int flag[M];
void add(int a,int b)
{
    nxt[++cent]=head[a];
    to[cent]=b;
    head[a]=cent;
}
struct dian{
    int in;
    int po;
    bool operator <(const dian &t)const 
    {
        return inin;
    }
}in[M];
int out[M];int vis[M];
int ans=0;
void dfs(int a,int fa)
{
    int tmp=1;vis[a]=1;
    for(ri p=head[a];p;p=nxt[p])
    {
        int b=to[p];
        if(vis[b]) continue;
        if(tmp==fa) tmp++;if(flag[a]==1) tmp=1;
        ans=max(ans,tmp);
        co[p]=tmp;
        co[p^1]=tmp;
        tmp++;
        dfs(b,co[p]);
    }
}
int main(){
    
    read(n);read(m);
    for(ri i=1;i)
    {
        int a,b;
        read(a);read(b);
        add(a,b);
        add(b,a);
        in[a].in++,in[b].in++;
        in[a].po=a;in[b].po=b;
    }
    sort(in+1,in+1+n);
    for(ri i=n;i>=(n-m+1);i--)
    {
        int a=in[i].po;
        flag[a]=1;
    }
    
    dfs(1,0);
    printf("%d\n",ans);
    for(ri i=2,j=1;j<=n-1;i+=2,j++)
    {
        printf("%d ",co[i]);
    }
    return 0;
    
    
    
    
    
    
    
    
    
    
}