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

题目大意：

2021ICPC南京H题
题目大意：给一棵树，大小为n（级别为1e5），你一开始在节点1的位置，每个节点上会a[i]只晶蝶，他们在你接近这个节点邻近的节点后会开始润，需要t[i]（只有1,2,3三种取值）时间润掉，然后你就抓不到它了，你单位时间只能走一步，要求大能捉住的晶蝶数量。

解：

推荐这题在看题解之前多自己想想。
好，首先我们可以轻易看出，当我们到达一个节点的时候，所有的最近子节点上的晶蝶都会被惊动，这个时候你肯定得抓啊，但是如果你抓完一个还不马上回来，那其他的肯定全跑了，如果你马上回来，那么t值为3的晶蝶还在，其他都没了，与此同时，你第一个抓的那只晶蝶的所有子节点都跑了。
这是不是有点类似于老板和员工只有一个上班的树形dp问题。
对于一个节点你只有两种选择：①拿完之后马上回来拿另一个t为3的晶蝶，②拿完之后我不回来，直接去拿别的。
那么我可以用此来定态：dp[i][0]表示拿完i晶蝶后马上回去时i的所有子节点抓到的最大晶蝶树木，dp[i][1]则是表示不马上回去时的。这里为什么是子节点而不直接算上本身稍后会说明，实际上是为了方便状态转移。
dp[i][0]的值很好转移，因为你马上回去了，i的所有子节点全跑了，因此对于i的所有子节点你都不存在拿一个再回到i再去拿另一个的操作，所以dp[i][0]就等于i的所有儿子的dp[son][1]之和。
而dp[i][1]呢，因为是不回去，所以你有两种选择，一种是我直接拿一个儿子上的晶蝶然后接着往下走，另一种是我拿一个儿子上的晶蝶再回头然后再去拿另外一个t值为3的晶蝶。我们要求的是这两种情况的最大值，也就是
max(wei[son]+∑dp[sons][1], wei[son]+wei[son2]+dp[son][0]-dp[son][1]+∑dp[sons][1])，
至于实现上可以使用multiset，也可以直接记录，实现上要注意一些细节，时刻记得这是一个整体的式子，不要去进行局部的贪心，multiset的复杂度完全是够用的。
最后要求的结果就是dp[1][1]了

实际上在vp的时候因为某些奇妙的bug做了两个多小时……其实是非常模板化的决策型树形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
84
85

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pint pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define maxn 200005
int wei[maxn],tag[maxn];
vector<int> tree[maxn];
int dp[maxn][2];

void dfs(int n,int dad){
	//cout<<"now dfsing "<<n<<endl;
	int siz=tree[n].size();
	multiset<int> st;
	//cout<<"siz is "<<siz<<endl;
	int ma=-1e18,ma2=-1e18,son2=-1,ma3=0,tt1=0;
	for(int i=0;i<siz;i++){
		int son=tree[n][i];
		if(son==dad)continue;
		dfs(son,n);
		tt1+=dp[son][1];
		if(tag[son]==3){
			st.insert(wei[son]);
		}
		ma3=max(wei[son],ma3);
	}
	dp[n][0]=tt1;
	ll ma4=0;
	st.insert(ma4);
	for(int i=0;i<siz;i++){
		int son=tree[n][i];
		if(son==dad)continue;
		if(tag[son]==3)st.erase(st.find(wei[son]));
		ma4=max(ma4, wei[son]+*st.rbegin()+dp[son][0]-dp[son][1]);
		if(tag[son]==3)st.insert(wei[son]);
	}
//	cout<<"ma4="<<ma4<<endl;
	dp[n][1]=max(ma3,ma4)+tt1;
//cout<<"dp."<<n<<"[0]="<<dp[n][0]<<endl;
//	cout<<"dp."<<n<<"[1]="<<dp[n][1]<<endl;
}
signed main(){
	std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)cin>>wei[i];
		for(int i=1;i<=n;i++)cin>>tag[i];
		for(int i=1;i<=n;i++){
			tree[i].clear();
			dp[i][0]=0;
			dp[i][1]=0;
		}
		int nn=n-1;
		while(nn--){
			int a,b;
			cin>>a>>b;
			tree[a].push_back(b);
			tree[b].push_back(a);
		}
		dfs(1,-1);
		cout<<dp[1][1]+wei[1]<<endl;
	}
	return 0;
} 
/*
8
8
1 1 1 1 1 1 1 1
1 3 2 1 3 2 1 3
1 2
1 3
1 4
2 5
2 6
5 7
5 8*/