Codeforces #633 Div1 B. Edge Weight Assignment

今回妙に解いてる人が多いけど、Div2の人でも多くが解ける問題だったってことかな。
https://codeforces.com/contest/1338/problem/B

問題

木を成す無向グラフが与えられる。
各辺に整数の重みを設定したとき、任意の葉の間のパス上の重みのxorが0となるようにしたい。
辺に設定する重みは最小/最大何通りとなるか。

解法

最小の方は簡単。
葉の頂点間の距離が全部偶数なら1種類。
そうでない場合、パスの長さは最低3以上あるので、例えば1,2,3の3つの値を使っていけばよい。

最大の方はある葉を根として以下のように処理していく。
任意に値が設定できる辺に、2^kを順次振っていくことにしよう。

• 子頂点に1個以上葉があるなら、それらに至る辺は、根から現在の頂点までの2^kの総和になるのでこれは初めて登場する値であり、1つ新たな値が現れる。
• 葉でない子頂点に対しては、未出現の2^kを割り当てればよいので、やはり1つ新たな値が現れる。

int N;
vector<int> E[101010];
int D[202020];
int C[2];
int ma;

void dfs(int cur,int pre,int d) {
	if(E[cur].size()==1) C[d]++;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d^1);
}

void dfs2(int cur,int pre,int d) {
	
	int leaf=0;
	FORR(e,E[cur]) if(e!=pre) {
		if(E[e].size()==1) {
			leaf++;
		}
		else {
			ma++;
			dfs2(e,cur,d+1);
		}
	}
	
	if(leaf && d!=1) ma++;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) if(E[i].size()==1) break;
	int root=i;
	dfs(0,0,0);
	
	int mi=1;
	if(C[0]&&C[1]) mi=3;
	dfs2(root,root,0);
	
	cout<<mi<<" "<<ma<<endl;
	
}

まとめ

もっとシンプルに書けそうな気もしてきた。