【Codeforces Round #547 (Div. 3) G. Privatization of Roads in Treeland】贪心+dfs

G. Privatization of Roads in Treeland

题意

给你一棵$n$个结点的树，现在要对每条边染色，如果一个节点所连接的边的颜色大于等于两种，则这个点是坏点，现在问如果要使坏点的个数不超过$k$，问最少要用多少种颜色去染边。

做法

首先由于这是一颗树，也就是每两个点只会被一条边影响，所以可以认为每个点染色是独立的。因为对于每条边至少染一种颜色，所以这条边如何染色不影响另一个点，之后我们贪心的选择度数最大的$k$个点去放弃这些点，然后从任意一点开始$dfs$染色即可。对于不放弃的点，他与所有子节点和父节点的边颜色均不相同。对于已放弃的点，全都染同一个色即可。最后统计最多用了几种颜色。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair <int, int> pii;
const int maxn = 2e5+5;
#define Fi first
#define Se second
#define pb push_back
struct data
{
    int pos;int ind;
}x[maxn];
vector<pii>G[maxn];
bool cmp(const data &a,const data &b)
{
    if(a.ind==b.ind) return a.pos<b.pos;return a.ind>b.ind;
}
int vis[maxn];
int ans[maxn];
void dfs(int rt,int fa,int col)
{
    int tmp=0;for(int i=0;i<G[rt].size();i++){
    int to=G[rt][i].Fi;int id=G[rt][i].Se;if(to==fa) continue;if(vis[rt]==1){
    ans[id]=1;dfs(to,rt,1);}else{
    if(++tmp==col) tmp++;ans[id]=tmp;dfs(to,rt,tmp);}}
}
int main()
{
    int n,k,u,v;scanf("%d%d",&n,&k);for(int i=1;i<=n-1;i++){
    scanf("%d%d",&u,&v);G[u].pb(pii(v,i));G[v].pb(pii(u,i));x[u].ind++;x[v].ind++;}for(int i=1;i<=n;i++) x[i].pos=i;sort(x+1,x+1+n,cmp);for(int i=1;i<=k;i++) vis[x[i].pos]=1;dfs(1,-1,-1);int maxx=0;for(int i=1;i<=n-1;i++) maxx=max(maxx,ans[i]);printf("%d\n",maxx);for(int i=1;i<=n-1;i++) printf("%d ",ans[i]);return 0;
}