F. Vlad and Unfinished Business
Link
题意： 给你一棵树，里面遍布几个任务点和一个目的地，求从出发点开始最短通过所有任务点最终到达目的地的最小步数。
思路： 记录从 x x x开始到达目的地 y y y的深度，并且把 y y y点也当个任务点，统计所有任务点沿径距离到出发点 x x x的距离和。最终再特殊处理 y y y，因为不用回到 x x x点，所以我们减去 y y y的深度即可，使用DFS实现。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
set<int>s;
const int N = 2e5+10;
int idx,e[N<<1],h[N],ne[N<<1];
int f[N];
bool st[N];
int dep[N];
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u,int fa,int deep){
dep[u]=deep;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==fa)continue;
f[j]=u;
dfs(j,u,deep+1);
}
}
void cf(){
int n,k;
cin>>n>>k;
int x,y;
cin>>x>>y;
s.clear();
idx=0;
for(int i=1;i<=n;i++){
dep[i]=0;
st[i]=false;
h[i]=-1;
}
for(int i=1;i<=k;i++){
int xx;
cin>>xx;
s.insert(xx);
}
for(int i=1;i<=n-1;i++){
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
for(int i=1;i<=n;i++)st[i]=false;
st[x]=true;
dfs(x,x,0);
s.insert(y);
int res=0;
for(auto g:s){
int gg=g;
while(!st[gg]){
st[gg]=true;
res+=2;
gg=f[gg];
}
}
cout<<res-dep[y]<<endl;
}
signed main(){
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t=1;
cin>>t;
while(t--){
cf();
}
}
