Codeforces Round #547 (Div. 3) G 贪心

https://codeforces.com/contest/1141/problem/G

题意

在一棵有n个点的树上给边染色,连在同一个点上的边颜色不能相同,除非舍弃掉这个点,问最少需要多少种颜色来染一棵树

题解

选择弃掉度数最高的k个点,然后第k+1个点的度数就是答案

代码

#include<bits/stdc++.h>

#define N 200005

#define pb push_back

using namespace std;

int n,k,u,v,in[N],c[N],m,i;

struct node{

	int e,v;

};

vector<node>g[N];

bool cmp(int x,int y){

	return x>y;

}

void dfs(int u,int fa,int cl){

	for(int i=0;i<g[u].size();i++){

		int v=g[u][i].v,id=g[u][i].e;if(v==fa)continue;

		if(cl>m)cl-=m;

		c[id]=cl++;

		dfs(v,u,cl);

	}

}

int main(){

	cin>>n>>k;

	for(i=1;i<=n-1;i++){

		scanf("%d%d",&u,&v);

		in[u]++;in[v]++;

		g[u].pb({i,v});

		g[v].pb({i,u});

	}

	sort(in+1,in+n+1,cmp);

	m=in[k+1];

	dfs(1,0,1);

	printf("%d\n",m);

	for(i=1;i<=n-1;i++){

		printf("%d ",c[i]);

	}

}

巴特西

Codeforces Round #547 (Div. 3) G 贪心

题意

题解

代码

最新文章

热门文章