求 Hack
查看原帖
求 Hack
583186
2c_s楼主2024/8/25 09:41
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,k,v[N],fa[N],dep[N],cnt;
bool vis[N];
vector<int>g[N];
void dfs(int x,int f){
	fa[x]=f;
	dep[x]=dep[f]+1;
	for(int i:g[x]){
		if(i==f)continue;
		dfs(i,x);
	}
	return ;
}
void lca(int x,int y){
	while(x^y){
		if(dep[x]<dep[y])swap(x,y);
		if(vis[x])return ;
		++cnt;
		x=fa[x];
	}
	return ;
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<n;++i){
		int u,v;
        cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=k;++i)cin>>v[i];
	dfs(1,0);
	sort(v+1,v+1+k,[](int x,int y){return dep[x]<dep[y];});
	for(int i=2;i<=k;++i)lca(v[i],v[1]);
	cout<<cnt+1;
	return 0;
}
2024/8/25 09:41
加载中...