思路
当 \(k = n\) 时，我们只需要用树上权值加和减去 \(s\) 到 \(t\) 的路径长度即可。
考虑对 \(s,t\) 是否在关键点组成的最小连通块内分类，记块内边权和为 \(sum\)。
若 \(s\) 和 \(t\) 都在连通块内，由特殊性质，当 \(s = t\) 只需恰经过每条边两次就可以走完，答案为 \(2 \times sum\)。那么一般地，当 \(s \neq t\) 时，无需再经过一次 \(s\) 到 \(t\) 的路径，减去这条树上简单路径长度即可。
否则，树上倍增求出二者到连通块的距离，加上上一种情况的答案。
Code
#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e5+5;
const int LogN=20;
int n,Q,k,head[N],nxt[N<<1],to[N<<1],w[N<<1],cnt=0,father[N][LogN],dep[N],dis[N],sum_connected=0,st,import[N];
bool in[N];
// int f=0;
void Add(int u,int v,int cost)
{to[++cnt]=v;w[cnt]=cost;nxt[cnt]=head[u];head[u]=cnt;
}
void Dfs_Connected(int u,int fa)
{if(!import[u]) return;in[u]=true;// cout<<u<<' ';// f++;for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;Dfs_Connected(v,u);if(in[v]) sum_connected+=w[i];}
}
void Dfs_Father(int u,int fa,int cost)
{dep[u]=dep[fa]+1,father[u][0]=fa,dis[u]=dis[fa]+cost;for(int i=1;i<LogN;i++)father[u][i]=father[father[u][i-1]][i-1];for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==fa) continue;Dfs_Father(v,u,w[i]);import[u]+=import[v];}
}
int LCA(int u,int v)
{if(dep[u]<dep[v]) swap(u,v);for(int i=LogN-1;i>=0;i--)if(dep[father[u][i]]>=dep[v])u=father[u][i];if(u==v) return u;for(int i=LogN-1;i>=0;i--)if(father[u][i]!=father[v][i])u=father[u][i],v=father[v][i];return father[u][0];
}
int Dis(int u,int v)
{return dis[u]+dis[v]-(dis[LCA(u,v)]<<1);
}
int Query(int u,int v)
{int fu=u,fv=v;if(!in[u]){for(int i=LogN-1;i>=0;i--)if(father[fu][i]&&!in[father[fu][i]])fu=father[fu][i];fu=father[fu][0];}if(!in[v]){for(int i=LogN-1;i>=0;i--)if(father[fv][i]&&!in[father[fv][i]])fv=father[fv][i];fv=father[fv][0];}return -Dis(fu,fv)+Dis(u,fu)+Dis(v,fv);
}
int main()
{// freopen("carrier.in","r",stdin);// freopen("carrier.out","w",stdout);IOS;cin>>n>>Q>>k;for(int i=1;i<n;i++){int u,v,cost;cin>>u>>v>>cost;Add(u,v,cost);Add(v,u,cost);}for(int i=1;i<=k;i++){cin>>st;in[st]=import[st]=1;}Dfs_Father(st,0,0);Dfs_Connected(st,0);// cout<<'\n';// cout<<st<<' '<<f<<' '<<sum_connected<<'\n';// for(int i=1;i<=n;i++) // if(in[i]) cout<<i<<' ';// cout<<'\n';while(Q--){int S,T;cin>>S>>T;cout<<(sum_connected<<1)+Query(S,T)<<'\n';}return 0;
}
完结撒花～