わりとすんなり思いつけた。
http://arc045.contest.atcoder.jp/tasks/arc045_c
問題
N頂点からなる木を成すグラフが与えられる。
各辺はコスト付の無向辺である。
2点間のコストは、頂点間の最短経路上の辺のコストのxorで与えられる。
頂点対(a,b)のうち、コストがXとなるものを求めよ。
解法
普通2点間の距離を求める手段として、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には数分遠かった。