実装は重いけど、考察はCより楽。
http://arc048.contest.atcoder.jp/tasks/arc048_d
問題
N頂点の木構造がある。
一部の頂点にはたこ焼きが配置されている。
頂点間を移動するとき、最初は1辺の移動に2の時間がかかるが、一度たこ焼きのある頂点を経由すると、以後移動にかかる時間が1になる。
(始点S[i],終点T[i])の対からなるクエリがQ個与えられる。
S[i]→T[i]に至る最短時間を求めよ。
解法
LCA+ダブリングで解いた。
グラフは木なので、たこ焼きを無視すると移動経路が一意に決まる。
あとは経路中のどこかで寄り道してたこ焼きを取るケースを考えよう。
頂点vに対し、最寄のたこ焼きがある頂点をf(v)とする。
DFSを2回行うと、各vに対しD(v,f(v))を求めることができる。
S→Tに至る途中頂点vで寄り道し、S→v→f(v)→v→Tと移動することを考えると、D(a,b)を頂点ab間の距離として移動にかかる時間はD(S,v)*2+D(v,f(v))*3+D(v,T)となる。
vを愚直に総当たりするとTLEする。
そこでグラフを根付き木と見なしダブリングを使おう。
以下の2値をダブリングで求める。
- 頂点vから途中どこかでたこ焼きを拾い、2^a個親の頂点に登る最短時間UP(v,a)
- 頂点vから2^a個親の頂点から途中どこかでたこ焼きを拾いvに降りる最短時間DOWN(v,a)
あとはS→LCA(S,T)に至る途中でたこ焼きを拾うケースの最短時間をUPを使って求め、またLCA(S,T)→Tに至る途中でたこ焼きを拾うケースの最短時間をDOWNを使って求め最小値を取る。
int N,Q; vector<int> E[101010]; string S; int MI[101010]; int P[21][200005],D[200005]; int upf[21][200005]; int upl[21][200005]; void dfs(int cur) { MI[cur]=(S[cur]==0)?10101010:0; ITR(it,E[cur]) if(*it!=P[0][cur]) { D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it); MI[cur]=min(MI[cur],MI[*it]+1); } } void dfs2(int cur,int p) { MI[cur]=min(MI[cur],p+1); ITR(it,E[cur]) if(*it!=P[0][cur]) dfs2(*it,MI[cur]); upf[0][cur]=upl[0][cur]=5000000; if(cur!=0) { upf[0][cur]=min(MI[cur]*3+1,2+MI[P[0][cur]]*3); upl[0][cur]=min(MI[cur]*3+2,1+MI[P[0][cur]]*3); } } int getpar(int cur,int up) { int i; FOR(i,20) if(up&(1<<i)) cur=P[i][cur]; return cur; } 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; cin>>N>>Q; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } cin>>S; FORR(r,S) r-='0'; dfs(0); dfs2(0,505050); FOR(i,19) { FOR(x,N) { P[i+1][x]=P[i][P[i][x]]; upf[i+1][x]=min(upf[i][x]+(1<<i),(2<<i)+upf[i][P[i][x]]); upl[i+1][x]=min(upl[i][x]+(2<<i),(1<<i)+upl[i][P[i][x]]); } } while(Q--) { int s,t; cin>>s>>t; s--,t--; int lc=lca(s,t); int ret=((D[t]-D[lc])+(D[s]-D[lc]))*2; if(s!=lc) { x=s; y=D[t]-D[lc]; for(i=19;i>=0;i--) if(D[x]-D[lc]>=(1<<i)) { int p=getpar(x,1<<i); ret=min(ret,y+upf[i][x]+(D[p]-D[lc])); x=p; y+=2<<i; } } if(t!=lc) { x=t; y=2*(D[s]-D[lc]); for(i=19;i>=0;i--) if(D[x]-D[lc]>=(1<<i)) { int p=getpar(x,1<<i); ret=min(ret,y+upl[i][x]+2*(D[p]-D[lc])); x=p; y+=1<<i; } } cout<<ret<<endl; } }
まとめ
HLは要らないと思った。