ABC 368D Minimum Steiner Tree

题意
给你一颗由N个点组成的树，指定K个节点，求包含这K个节点的最小子树的大小

思路
考虑正难则反，我们从开始的树当中剪掉那些没有任何指定点的子树，剩下来的子树就是最小的、能包含所有指定节点的子树。关于剪去这个操作，就是dfs一旦遇到以当前节点为根的子树没有任何指定点时，就停止dfs，并把该子树的大小贡献到much里。最后用n减去much，就是答案（注意选根的时候要注意，用指定的某个点作为根来进行dfs，否则这个方法会被菊花图给hack掉）

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10;
int a[maxn],sz[maxn],much;
vector<int>ds[maxn];

void dfs1(int u,int fa)
{
	sz[u]=1;
	for(int i=0;i<ds[u].size();i++)
	{
		int v=ds[u][i];
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		a[u]+=a[v];
	}
}

void dfs2(int u,int fa)
{
	if(!a[u])
	{
		much+=sz[u];
		return ;
	}
	for(int i=0;i<ds[u].size();i++)
	{
		int v=ds[u][i];
		if(v==fa) continue;
		dfs2(v,u);
	}
}


signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		ds[u].push_back(v);
		ds[v].push_back(u);
	}
	int begin;
	for(int i=1;i<=k;i++) 
	{
		int x;
		cin>>x;
		begin=x;
		a[x]=1;
	}
	dfs1(begin,0);
	dfs2(begin,0);
	cout<<n-much<<endl;
	
	
	return 0;
}