Mail.Ru Cup 2018 Round 2 : F. Tree and XOR

微妙に状態遷移が思いつかず。
http://codeforces.com/contest/1055/problem/F

問題

N頂点からなる木を成すグラフが与えられる。
各辺にはコストが整数値で設定されており、2頂点間のコストは両頂点を結ぶパスの各辺のコストのxorを取った値とする。

2頂点対N^2通りについて、コストを列挙したとき小さい順にK番目の値は何か。

解法

f(u,v) := u,v間のコスト
とするとf(u,v) = f(root,u) xor f(rott,v)
と置けるので、g(v)=f(root,v)を各頂点について計算しておけば、あとはg(u) xor g(v)をN^2通り考えるだけで良くなり、グラフの形状は気にしなくて良くなる。

Editorialは各値をTrieで分類してO(N*max(g(v))の解法を記載していたが、以下O(NlogN*max(g(v))だけど実装が容易な方法を示す。
解について上のbitから決めていくことにする。
今d bit目を決めることにしよう。下から(d+1) bit目までは確定済みで、その値をRとする。
d bit目を0にした場合を仮定する、g(u) xor g(v)のうち(d+1)bit目以上がRと一致し、d bit目が0となる組がP個あったとする。
K≦Pなら、d bit目は0にするのが良く、K＞Pならd bit目を0にしたものではK個に満たないので、d bit目を1にしつつK -= PでKを更新すればよい。

「g(u) xor g(v)のうち(d+1)bit目以上がRと一致し、d bit目が0となる組」の求め方だが、(g(v)^R)を先にソートしておき、またg(u)を小さい順に処理していけば尺取り法の要領で(g(v)^R)の(d+1)bit目以上がg(u)と一致するものをO(N)で求められる(ソートは別途O(NlogN)。

int N;
ll K;
ll V[1010101];
ll T[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%" PRId64, &N,&K);
	FOR(i,N-1) {
		scanf("%d%" PRId64, &x,&V[i+1]);
		V[i+1]^=V[x-1];
	}
	sort(V,V+N);
	
	ll ret=0;
	for(i=61;i>=0;i--) {
		FOR(j,N) T[j]=(V[j]^ret)>>i;
		sort(T,T+N);
		
		int L=0,R=0;
		ll sum=0;
		FOR(j,N) {
			ll v=V[j]>>i;
			while(L<N&&T[L]<v) L++;
			while(R<N&&T[R]<=v) R++;
			sum+=R-L;
		}
		
		if(sum<K) {
			K-=sum;
			ret^=1LL<<i;
		}
		
	}
	cout<<ret<<endl;
}

まとめ

本番途中1になるbitがある場合を綺麗に処理できなかったのだが、これはシンプルでいいな。
上位の桁が一致するグループを管理すれば、間のソートも削減できそう。