Codeforces #547: Div3. G. Privatization of Roads in Treeland

途中結構ミスしてるがなぜか１位になれた回。
https://codeforces.com/contest/1141/problem/G

問題

N点の木を成す無向グラフと、正整数Kが与えられる。
各辺をR色で彩色するとき、同じ色の辺２本以上を端点に持つ点の数をK以下にしたい。
Rの最小値と彩色例を求めよ。

解法

次数の多い点の上位K点を、同じ色の辺を２本以上持ってよい点とする。
すると、Rは(K+1)番目の点の次数となる。
あとはR色で各辺を彩色していけばよい。

int N,K,R;
vector<pair<int,int>> E[202020];
vector<pair<int,int>> C;
int col[202020];

void dfs(int cur,int pre,int pc) {
	
	if(E[cur].size()>R) {
		if(pc==-1) pc=0;
		FORR(e,E[cur]) if(e.first!=pre) {
			col[e.second]=pc;
			dfs(e.first,cur,pc);
		}
	}
	else {
		int c=0;
		FORR(e,E[cur]) if(e.first!=pre) {
			if(c==pc) c++;
			col[e.second]=c;
			dfs(e.first,cur,c);
			c++;
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back({y-1,i});
		E[y-1].push_back({x-1,i});
	}
	FOR(i,N) C.push_back({E[i].size(),i});
	sort(ALL(C));
	while(K) {
		C.pop_back();
		K--;
	}
	R=C.back().first;
	dfs(0,0,-1);
	
	cout<<R<<endl;
	FOR(i,N-1) cout<<col[i]+1<<" ";
	
}

まとめ

一見ややこしいけど実際はそこまででもなかった。