1 条题解
-
0
以随意一个指定顶点本代码中用的是为根,建树,遍历树上每个点,只要以这个点为根的子树内有指定顶点,这个点就必须保留在新的树上,最小顶点数加。为以为根的子树中指定顶点的个数
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int sz[N],rt,ans; vector<int>e[N]; void dfs(int x,int xfa) { for(int y:e[x])if(y!=xfa) { dfs(y,x); sz[x]+=sz[y]; } if(sz[x]>0)ans++; return; } int main() { memset(sz,0,sizeof sz); int n,k;scanf("%d%d",&n,&k); for(int i=1,x,y;i<n;i++) { scanf("%d%d",&x,&y); e[x].push_back(y); e[y].push_back(x); } for(int i=1;i<=k;i++) scanf("%d",&rt),sz[rt]=1; dfs(rt,0); printf("%d\n",ans); return 0; }
- 1
信息
- ID
- 7973
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 7
- 标签
- 递交数
- 29
- 已通过
- 7
- 上传者