1 条题解

  • 0
    @ 2025-12-15 20:28:22

    以随意一个指定顶点( ( 本代码中用的是Vk) V_k) 为根,建树,遍历树上每个点,只要以这个点为根的子树内有指定顶点,这个点就必须保留在新的树上,最小顶点数ans ans 11SZi SZ_i ( ( i i 为根的子树中指定顶点的个数) )

    #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
    上传者