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

题目大意：

CF192D Book of Evil
众所周知之前做了道假的双向树形dp，这次这个是真的了……
题目大意：给一棵树，有n个节点（1e5），m个被污染的点，一个d值，求树上距离这m个点最远距离不超过d的节点数量。

解：

由于一个结点通过子树达到的最远距离可以通过后序遍历轻松得出，而除此之外只有通过父亲的走法，这样走到的最远距离即是先走到父亲结点再走到父亲结点能走到的最远距离对应的路（除了本身所在的路）
最为典型的双向树形dp，第一次后序遍历的时候用vector或者优先队列保存下来每一个子树传上来的距离，传完之后进行排序，之后进行一次前序遍历，通过之前保存的距离，先判断是否是原先走过的距离，之后向下推。有个细节就是：前序遍历时，如果子节点已经有值，那么父亲节点必须有大于两个值时才能去转移（否则那个唯一的值肯定是该子节点传上来的），但如果子节点没有值，那么父亲节点即使只有一个值也要传下去，不过其实如果写法足够严谨的话是不需要担心这个问题的。
如果用stl的话要注意各种越界问题，如果都照顾到的话这题算是一道水题。

代码

代码
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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 1000000007
#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);
#define pll pair<ll,ll>
#define inc(i,a,n) for(ll i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
using namespace std;
ll ans,d,vis[maxn];
vector<ll> tree[maxn], dp[maxn];
bool cmp(ll l1, ll l2) { return l1 > l2; }
void dfs(int n, int dad) {
	if (vis[n] == 1)dp[n].push_back(0);
	for (int i = 0; i < tree[n].size(); i++) {
		int son = tree[n][i];
		if (son == dad)continue;
		dfs(son, n);
		if(dp[son].size())dp[n].push_back(dp[son][0]+1);
	}
	sort(dp[n].begin(), dp[n].end(),cmp);
}
void dfs2(int n, int dad) {
	
	for (int i = 0; i < tree[n].size(); i++) {
		int son = tree[n][i];
		if (son == dad)continue;
		if (dp[n].size() >= 2) {
			if (dp[son].size() && dp[son][0] + 1 == dp[n][0]) {
				dp[son].push_back(dp[n][1]+1);
			}
			else {
				dp[son].push_back(dp[n][0]+1);
			}
		}
		else if (dp[n].size() >= 1&&dp[son].size()==0) {
			dp[son].push_back(dp[n][0] + 1);
		}
		sort(dp[son].begin(), dp[son].end(),cmp);
		dfs2(son, n);
	}
	if (dp[n][0] <= d)ans++;
}
int main() {
	cfast;
	ans = 0;
	int n, m;
	cin >> n >> m >> d;
	inc(i, 0, m) {
		ll mon;
		cin >> mon;
		vis[mon] = 1;
	}
	inc(i, 0, n - 1) {
		ll a, b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs(1, -1);
	dfs2(1, -1);
	cout << ans;
}//((()