把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1611E2 Escape The Maze(harder version)

题目大意，给一个树（大小规模为1e5），你从1开始，想要逃到别的子节点，树上有k个朋友（位置给出），你和朋友同时开始移动，只要被朋友抓到你就寄了。现在朋友想要省点体力所以他们想用最小的人数抓到你，让你求出最小需要几个人，如果所有人都上还抓不到那你就赢了，输出-1。

解：

很容易想到，当一个朋友在你来一棵子树之前就站在这棵子树的根上，那么这个子树就不需要其他人了，而达成这个目标的条件是朋友到这个根的距离小于等于“1”到这个根的距离，于是我进行两次dfs，第一次找每棵子树是否存在一个这样的朋友能直接站在子树的根上，如果能，我打个标记，这棵子树我只需要一个人就够了。之后我进行第二次dfs，这一次的dfs就是直接返回需要的人数了，凡是打过标记的我直接返回1，否则往下继续搜索，碰到打标记的还是返回1，否则搜到路上第一个有朋友的点，如果说搜到了叶子节点还没有找到朋友，那么我就可以从这条路成功逃脱。
由于最优性的缘故还是把它归类在树形dp里了，实际上应该只能算是记忆化搜索吧。
有一说一，做这题的时候满脑子都是“想和露娜做朋友吗？”……
1900分对于树形DP还是过于早了呀。什么树分治，我不知道，没听说过，这是数据结构选手应该做的吧。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll vis[maxn], dp[maxn];
int f;
vector<ll> sons[maxn];
int dfs1(int now, int from,int level) {
	if (vis[now] == 1)return level;
	int ans = 1e9;
	for (int i = 0; i < sons[now].size(); i++) {
		if (sons[now][i] == from)continue;
		ans = min(ans, dfs1(sons[now][i], now, level + 1));
	}
	if (ans - level <= level)dp[now] = 1;
//	cout << "dfs1." << now << "=" << ans << endl;
	return ans;
}
int dfs2(int now, int from) {
	if (dp[now] == 1)return 1;
	if (vis[now] == 1)return 1;
	int ans = 0;
	for (int i = 0; i < sons[now].size(); i++) {
		if (sons[now][i] == from)continue;
		ans += dfs2(sons[now][i], now);
	}
	if (ans == 0) {
		f = 1;
	}
	return ans;
}
int main()
{
	cfast;
	int t;
	cin >> t;
	while (t--) {
		f = 0;
		int n,k;
		cin >> n >> k;
		while (k--) {
			int d;
			cin >> d;
			vis[d] = 1;
		}
		for (int i = 1; i < n; i++) {
			int a, b;
			cin >> a >> b;
			sons[a].push_back(b);
			sons[b].push_back(a);
		}
		dfs1(1, -1, 0);
		int ans = dfs2(1, -1);
		if (f == 1)cout << "-1" << endl;
		else cout << ans << endl;
		clr(vis, n+1);
		clr(dp, n + 1);
		for(int i=1;i<=n;i++)sons[i].clear();
	}


}
/*
2
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
*/