F. Vlad and Unfinished Business
和一般的求多个点都到达的最小距离不同
这里规定了终点 这样我们首先x-y这条链可以确定
当然我们这条链可以通过让path[y]等于1 因为树中两点距离确定所以链一定 我们直接通过return时就可以确定链
然后我们还要确定的就是这个子树中有没有关键点
要是没有显然不用进入的
然后我们可以基于这条链把整颗树补全
然后就好做了 我们只需求这条链上每一个子树get到点的最小距离即可
这里可以直接贪心 直接返回距离即可
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int n,k,x,y,a[N],path[N],son[N];
vector<int>g[N];
int dfs1(int u,int fa){
for(auto v:g[u]){
if(fa==v)continue;
son[u]+=dfs1(v,u);
path[u]|=path[v];
}
return son[u];
}
int dfs2(int u,int fa){
int res=0;
for(auto v:g[u]){
if(fa==v)continue;
if(!path[v]&&son[v])res+=dfs2(v,u)+2;
}
return res;
}
void solve() {
cin>>n>>k>>x>>y;
for(int i=1;i<=n;i++)son[i]=path[i]=0,g[i].clear();
for(int i=1;i<=k;i++){
cin>>a[i];
son[a[i]]=1;
}
path[y]=1;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(x,0);
int ans=0;
for(int u=1;u<=n;u++){
if(path[u])ans+=dfs2(u,0);
}
cout<<ans+count(path+1,path+n+1,1)-1<<endl;
}
signed main(){
fast
int t;t=1;cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:787,return,int,Codeforces,son,fa,path,Round,const
From: https://www.cnblogs.com/ycllz/p/16788276.html