P6227 [BalticOI 2019 Day1] 山谷
Description
给一棵树，一个根，一些特殊补给点，一些询问。求解如下问题：断掉一条边 \(u\to v\)，这样以后你能否从给定的 \(R_i\) 走到根，若能输出 escaped。不能到达根且不能到达任何一个特殊补给点输出 oo。若不能到达根但可以到达特殊补给点输出边权和最小值。
Solution
我们考虑断边 \(u\to v\) 之后的情形，为方便描述我们设 \(fa_v=u\)。
我们考虑不能从给定的 \(R_i\) 走到根的情况，即 \(\operatorname{LCA}(v,R)= v\) 时，则我们有如果能走到根，则必有 \(\operatorname{LCA}(v,R)\ne v\)，则第一种情况解决完毕。
下面考虑设 \(\_shop_i\) 表示 \(i\) 及 \(i\) 的子树内特殊补给点的个数，可以考虑使用 dfs 进行预处理，那么不能到达根且不能到达任何一个补给点的充要条件为 \(\operatorname{LCA}(v,R)=v\) 且 \(\_shop_v=0\)。
最后考虑最难的一种情况，即不能到达根但可以到达特殊补给点。设 \(dis_i\) 表示编号为 \(i\) 的点到根的边权和，设到达的最近特殊补给点编号为 \(id\)，设 \(R\) 和 \(id\) 的 \(\operatorname{LCA}\) 为 \(\_lca\) ，设这个 \(\operatorname{LCA}\) 到 \(id\) 的距离为 \(W_{\_lca}\)，则我们有 \(Ans=dis_R-dis_{\_lca}+W_{\_lca}\)。我们考虑复杂度瓶颈，即不能暴力枚举所有 \(v\) 子树内的点作为 \(\operatorname{LCA}\)，则我们考虑倍增优化。
设 \(f_{i,j}\) 表示编号为 \(i\) 的点向上跳 \(2^j\) 步范围内最近的满足上段条件的 \(\operatorname{LCA}\) 所产生的贡献 \(-dis_{\_lca}+W_{\_lca}\)。则我们有如果该点为特殊补给点则 \(f_{i,0}=0\)。而后我们考虑预处理 \(f_{i,j}=\min(f_{i,j-1},f_{fat_{i,j-1},j-1})\)。
每次询问枚举跳 \(2^j\) 步，每次如果 \(dep_{fat_{x,j}}\ge dep_v\)（即不能跳出被截断的子树）就继续往上跳找答案，即 \(res=\min(res,f_{x,j})\)，最后 \(ans=\min(ans,f_{v,0})\)。别忘了这时的 \(ans\) 不是最终答案，需要 \(Ans=ans+dis_R\)。得出最后的 \(Ans\)。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,s,q,e;
const int N=2e5+7;
vector<pair<int,int> > G[N<<1];
int top[N<<1];
int fa[N<<1],bgs[N<<1],dep[N<<1],siz[N<<1];
int U[N<<1],V[N<<1],W[N<<1];
int shop[N<<1];
int f[N][30];
int _shop[N<<1];
int fat[N][30];
int dis[N];
void dfs(int x,int fat){
if(shop[x]) f[x][0]=0;
_shop[x]=shop[x];
dep[x]=dep[fat]+1;
fa[x]=fat;siz[x]=1;
for(auto it:G[x]){
int k=it.first,w=it.second;
if(k!=fat){
dis[k]=dis[x]+w;
dfs(k,x);
f[x][0]=min(f[x][0],f[k][0]+w);
_shop[x]+=_shop[k];
siz[x]+=siz[k];
if(siz[k]>siz[bgs[x]]) bgs[x]=k;
}
}
}
void DFS(int x,int fat,int tp){
top[x]=tp;
if(bgs[x]){
DFS(bgs[x],x,tp);
}
for(auto it:G[x]){
int k=it.first;
if(k!=fat&&k!=bgs[x]) DFS(k,x,k);
}
}
int lca(int x,int y){
while(top[x]^top[y]) dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
void work(int I,int R){
int u=U[I],v=V[I];
if(fa[v]!=u) swap(u,v);
if(lca(v,R)!=v) return printf("escaped\n"),void();
if(lca(v,R)==v&&_shop[v]==0) return printf("oo\n"),void();
int x=R;
int res=0x3f3f3f3f3f3f3f3fll;
for(int j=18;j>=0;j--){
if(dep[fat[x][j]]>=dep[v]){
res=min(res,f[x][j]);
x=fat[x][j];
}
}
res=min(res,f[v][0]);
res+=dis[R];
printf("%lld\n",res);
}
void debug(){
for(int i=1;i<=n;i++) printf("%lld ",dis[i]);
puts("");
}
signed main(){
memset(f,0x3f,sizeof f);
scanf("%lld%lld%lld%lld",&n,&s,&q,&e);
for(int i=1;i<n;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
G[u].push_back(make_pair(v,w)),G[v].push_back(make_pair(u,w));
U[i]=u,V[i]=v,W[i]=w;
}
for(int i=1;i<=s;i++) {int pos;scanf("%lld",&pos);shop[pos]=1;}
dfs(e,0),DFS(e,0,e);
for(int i=1;i<=n;i++){
f[i][0]-=dis[i];
}
for(int i=1;i<=n;i++) fat[i][0]=fa[i];
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
fat[i][j]=fat[fat[i][j-1]][j-1];
f[i][j]=min(f[i][j-1],f[fat[i][j-1]][j-1]);
}
}
for(int i=1;i<=q;i++) {int I,R;scanf("%lld%lld",&I,&R),work(I,R);}
}