こちらは不参加なので復習のみ。
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; }
まとめ
これは普通に自力で思いつけた。