E2. escape the maze (hard version)

Codeforces Round #756 (Div. 3)

Problem

There is one n A maze of points , Maze has n - 1 side , It's a tree .A Yes k A friend .A At the node 1,k A friend is k Two different nodes . Every second, everyone can move to an adjacent node , You can reach the same node at the same time .A And his friends can meet at the same node or at the midpoint of a side . If A Without meeting his friends , You can move to any leaf node , A win victory , otherwise A Our friends won .
ask ： If A Your friend wins , this k At least a few individuals can catch A.

Solution

1. First consider A How to win
   If A Minimum distance to leaf node Less than A The minimum distance to all friends , that A Win . The reverse is A Our friends won .

2. A Your friend wins , Solve the minimum number of friends

   1. hypothesis
      Friend node ： The node of a friend is a friend node
      A node x Have solution ：A If you pass x node ,A Will be caught by his friends
      A node x unsolvable ：A Can pass x The node reaches a leaf node
   2. Have solution ：
      ①x There is a friend node to x Distance of Less than or equal to A To x Distance of ,
      At this time, the solution is ：1
      （ because A This friend can arrive in advance x node , And then grab A）
      ②x All the friends in the node of... Go to x Distance of Greater than A To x Distance of , And x All child nodes of have solutions ,
      At this time, the solution is ：x Sum the solutions of all child nodes of
      （ if x A child node of has no solution , that A You can win through this node . That is, there is no solution ）
   3. unsolvable ：
      x All the friends in the node of... Go to x Distance of Greater than A To x Distance of , And there are nodes without solutions in its child nodes .
      perhaps x A leaf node that is not a friend node （ if x Is a friend node , It's also a leaf node , obviously x Nodes have solutions ）

3. All in all , This question is very convoluted ... It takes patience to ponder

Code

const int N = 2e5 + 5, M = 4e6 + 7;
vector<int> v[N];
int a[N], d[N], near[N];
int n, k;

int dfs(int x, int fa)
{
    
	int sum = 0; bool flag = 1;// Subtree and 、 Whether there is a subtree without solution 
	for (int y : v[x])
	{
    
		if (y == fa) continue;
		d[y] = d[x] + 1;
		int c = dfs(y, x);
		if (c < 0) flag = 0;
		else sum += c;
		near[x] = min(near[x], near[y] + 1);
	}
	if (near[x] <= d[x]) return 1;// As long as there is a friend node, you can arrive first x There is a solution , Even if there are child nodes, there is no solution 
	if (sum == 0 || flag == 0) return -1;//x There are no child nodes and x Not a friend node   perhaps   There is a child node without solution , be x Node has no solution 
	return sum;
}

int main()
{
    
	IOS;
	int T; cin >> T;
	while (T--)
	{
    
		cin >> n >> k;
		for (int i = 1; i <= n; i++)
		{
    
			v[i].clear();
			near[i] = inf;
			d[i] = 0;
		}
		for (int i = 1; i <= k; i++)
		{
    
			cin >> a[i];
			near[a[i]] = 0;
		}
		for (int i = 1, x, y; i < n; i++)
		{
    
			cin >> x >> y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		
		cout << dfs(1, -1) << endl;
	}


	return 0;
}