AtCoder ARC #045 : C - エックスオア多橋君

わりとすんなり思いつけた。
http://arc045.contest.atcoder.jp/tasks/arc045_c

問題

N頂点からなる木を成すグラフが与えられる。
各辺はコスト付の無向辺である。

２点間のコストは、頂点間の最短経路上の辺のコストのxorで与えられる。
頂点対(a,b)のうち、コストがXとなるものを求めよ。

解法

普通２点間の距離を求める手段として、a→LCA(a,b)の距離とLCA(a,b)→bの和を足す方法がある。
ただ、今回はコストは和でなくxorで計算されるので、a→LCA(a,b)のコストとLCA(a,b)→bのコストのxorを取ったものは、a→LCA(a,b)→root→LCA(a,b)→bと一旦根まで行った場合の各辺のコストのxorと等しい。
(LCA(a,b)と根の往復分はxorで相殺される)

よってこの問題は、各頂点xの根から至る各辺のコストのxorを取ったものをD(x)とすると、D(a)^D(b)=Xとなる(a,b)の数を求める問題と見なすことができる。
まずD(x)=pとなるような頂点数F(p)を求めよう。

• X==0の場合
  • D(x)が同じ頂点のペアが答えとしてカウントされるため、各pについてF(p)*(F(p)-1)/2を足す
• X!=0の場合
  • 各aについて、D(a)^p=Xとなるpすなわちp=X^D(a)を考えると、F(p)の分答えにカウントされる。ただしこの手法は(a,b)と(b,a)を二重カウントするので全体を半分だけカウントするようにする。

int N;
ll X;
vector<pair<int,int>> E[101010];
ll tot[101010];
map<ll,ll> M;

void dfs(int cur,int pre,int t) {
	tot[cur]=t;
	FORR(r,E[cur]) if(r.first!=pre) dfs(r.first,cur,t^r.second);
	M[t]++;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N-1) {
		cin>>x>>y>>r;
		E[x-1].push_back({y-1,r});
		E[y-1].push_back({x-1,r});
	}
	dfs(0,-1,0);
	
	ll ret=0;
	if(X==0) {
		FORR(r,M) ret+=r.second*(r.second-1)/2;
	}
	else {
		FORR(r,M) {
			ll r2=r.first^X;
			if(r.first<r2) ret+=r.second*M[r2];
		}
	}
	cout<<ret<<endl;
}

まとめ

わりと早く思いついたけど、FAには数分遠かった。