Bubble Cup 8 Final : B. Bribes

こちらは不参加なので復習のみ。
http://codeforces.com/contest/575/problem/B

問題

N頂点からなる木が与えられる。
各辺は両方向移動可能の辺と、一方通行の辺のどちらかである。
ただし、罰金を払うことで一方通行の道も逆流できる。
ある頂点間を移動する間、途中でx個の辺を逆流すると2^xだけ罰金が必要となる。

ここでK個の頂点列が与えられる。
それらを順に辿る場合、払う必要のある最小の罰金はどの程度か。

解法

グラフを根付き木と見なし、DFSして各頂点iに対し根から各頂点iまでの

• 親方向の移動が逆流となる辺の数P[i]
• 子方向の移動が逆流となる辺の数C[i]

を求めよう。
次にダブリングでLCAを求める準備をしておく。

x→yに移動する場合、x→lca(x,y)に移動する際の逆流回数P[x]-P[lca(x,y)]と、lca(x,y)→yに移動する際の逆流回数C[y]-C[lca(x,y)]の和が移動時の逆流回数となる。

int N,K;
ll fact2[1010100];
ll mo=1000000007;
ll ret;

vector<int> E[101010];
int P[21][100005],D[100005];
int up[101010],down[101010];
map<pair<int,int>,int> mp;

void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}
void dfs2(int cur,int pre) {
	ITR(it,E[cur]) if(*it!=pre) {
		dfs2(*it,cur);
		up[cur]+=up[*it];
		down[cur]+=down[*it];
	}
	if(mp[{cur,pre}]) ret += fact2[up[cur]]+mo-1;
	if(mp[{pre,cur}]) ret += fact2[down[cur]]+mo-1;
}

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	FOR(i,N-1) {
		scanf("%d%d%d",&x,&y,&r);
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
		mp[{x-1,y-1}]=0;
		mp[{y-1,x-1}]=r;
	}
	
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	
	fact2[0]=1;
	FOR(i,1000005) fact2[i+1]=fact2[i]*2%mo;
	
	scanf("%d",&K);
	int cur=0,tar;
	FOR(i,K) {
		scanf("%d",&tar);
		tar--;
		int lc = lca(cur,tar);
		up[cur]++,up[lc]--;
		down[tar]++,down[lc]--;
		cur=tar;
	}
	dfs2(0,-1);
	
	cout<<ret%mo<<endl;
}

まとめ

これは普通に自力で思いつけた。