P9433 [NAPC-#1] Stage5 - Conveyors
题意简述
给定一个\(N\)个节点的树形结构，每条边有边权，树上有\(k\)个关键点。
接下来有\(q\)次询问，每次询问给定\(x,y\)两点，请计算从\(x\)开始经过这\(k\)个关键点（可以重复经过）再到\(y\)的最短路程。
解题思路
我们可以发现，如果\(x\)与\(y\)都在\(k\)个关键点所形成的最小子图中，那么答案就是这个子图中所有边长度之和\(w\)的两倍，再减去\(x\)到\(y\)的距离，即\(2w-dist(x,y)\)。
为什么呢？因为除了\(x\sim y\)之间的边只需要走\(1\)次，其他边都需要走来回\(2\)次。
那如果\(x,y\)不全在这个子图中呢？那么我们就把\(x,y\)移到里面去，用\(2w-dist(x',y')\)再额外加上移动的距离即可。
为了方便操作，我们把关键点之一当作根节点，这样该子图就一定包含根节点了。
接下来，我们就可以用倍增把\(x,y\)跳到子图中，顺便计算出跳跃的距离，累加到\(2w-dist(x',y')\)中即可。
怎么求跳跃的距离呢？我们用\(dis[u][i]\)表示\(u\)节点往上\(2^i\)层的边权之和，在预处理LCA时计算出来。倍增跳跃时，每跳一次累加一下\(dis\)，最终结果就是跳跃距离了。
怎么求\(dist(x,y)\)呢？根据上面的定义，\(dis[u][19]\)足以表示\(u\)到根节点的距离，那么有\(dist(x,y)=dis[x][19]+dis[y][19]-2\times dis[lca(x,y)][19]\)。
（一开始我的思路比较傻，是在倍增求LCA的过程中，每跳一步累加一次\(dis\)。这样显然不如上面优啦）
\(\texttt{<Code/>}\)
点击查看代码
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,k,q,root,w;
struct edge{int to,w;};
vector<edge> G[N];
bool is[N];
int dep[N],fa[N][20],dis[N][20];
void dfs(int u,int father){
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=1;i<20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1],
dis[u][i]=dis[u][i-1]+dis[fa[u][i-1]][i-1];
for(auto i:G[u])
if(i.to!=father){
dis[i.to][0]=i.w;
dfs(i.to,u);
if(is[i.to])
is[u]=1,
w+=i.w;
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>=dep[v])
u=fa[u][i];
if(u==v) return u;
for(int i=19;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int dist(int u,int v){
return dis[u][19]+dis[v][19]-2*dis[lca(u,v)][19];
}
int jump(int &x){
int ans=0;
for(int i=19;i>=0;i--)
if(fa[x][i]&&!is[fa[x][i]])
ans+=dis[x][i],
x=fa[x][i];
ans+=dis[x][0],x=fa[x][0];
return ans;
}
int main(){
cin>>n>>q>>k;
for(int i=1;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back({v,w});
G[v].push_back({u,w});
}
for(int i=1;i<=k;i++){
cin>>root;
is[root]=1;
}
dfs(root,0);
w*=2;
while(q--){
int x,y;
cin>>x>>y;
int ans=0;
if(!is[x]) ans+=jump(x);
if(!is[y]) ans+=jump(y);
ans+=w-dist(x,y);
cout<<ans<<"\n";
}
return 0;
}