鄙人第一次寫博客，觀感不好請見諒（狗頭保命）
管他什么DP來了做法都一樣
確定狀態定義->明確子問題->確定狀態轉換方程->找邊界->打表驗證
樹形其實也就只是在樹上跑DP而已
一般兩種遍歷順序：
1.自上而下
2.自下而上

今天我們先來討論討論先是第一種情況：以自上而下的順序跑DP
洛谷P1352 沒有上司的舞會
這玩意是個經典的樹形dp

確定狀態定義：

每個職員要么來要么不來，兩種狀態我們很顯然可以分開來維護：
設
f(i,0)為i職員不參加舞會時的最大快樂值
f(i,1)為i職員來參加舞會時的最大快樂值

明確子問題

很顯然，某個職員來不來和他的上司來不來有著直接的關系嘛
所以說我們可以通過員工節點來維護他的上司節點
當某位員工的上司不來的時候他可以選擇來或者不來
但要是上司來了，那這位員工可就不能來了
所以......

確定狀態轉化方程

f(i,1)表示i職員參加舞會的最大值，而他參加了他的下屬就肯定不會再來參加
所以我們可以得到：

其中一條就出來了！
那看看該職員不來的情況呢？
當員工i不來參加時，他的下屬可以選擇來或者不來，而f維護的是最大快樂值
所以我們可以得到：

好的，這下完整的狀態轉移方程就解決啦！

確定邊界條件

開頭也說過，這道題是自下而上的遍歷順序
我們來好好分析一下
在確定狀態轉移方程的時候，我們知道了，f(i,0)和f(i,1)都是由他的員工，即他的孩子節點來維護的
要是某位員工沒孩子(bushi)......
要是某位員工沒有下屬，即這位員工他是個樹上的葉子節點呢？
那該員工來參加是的最大快樂值就只能是他自己的快樂值了，可憐的底層社畜......
綜上，我們可以得到：

，

，

打表驗證就不呈現出來啦，自己造一組數據手搓結果就行（）

上代碼

#include<bits/stdc++.h>
using namespace std;
//const int MAXN=1003;某人第一遍敲的時候RE原因實錄...眼是真瞎... 
const int MAXN=6005；
struct node
{
	int fa=0,r=0;
	bool leaf=0;    //注意初始化
	vector<int> son;
}tr[MAXN];
int n,dp[MAXN][2],vis[MAXN],root;
void dfs(int v)
{
	vis[v]=1;
	if(tr[v].leaf)
		return;
	for(int w=0;w<tr[v].son.size();w++)
		if(!vis[tr[v].son[w]]) 
			dfs(tr[v].son[w]);
	dp[v][1]=tr[v].r;
	dp[v][0]=0;
	int child;		//加個中間量讀起代碼來好讀一點（） 
	for(int i=0;i<tr[v].son.size();i++)
	{
		child=tr[v].son[i];
		dp[v][1]+=dp[child][0];
		dp[v][0]+=max(dp[child][1],dp[child][0]);
	}
	return;
}
int main()
{
	int l,k;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>tr[i].r;
	for(int i=1;i<=n-1;i++)
	{
		cin>>l>>k;
		tr[l].fa=k;
		tr[k].son.emplace_back(l);
	}
	for(int i=1;i<=n;i++)
	{ 
		if(tr[i].fa==0)		//查找根節點 
			root=i;
		if(tr[i].son.size()==0)
		{
			tr[i].leaf=1;
			dp[i][0]=0;
			dp[i][1]=tr[i].r;
		}
	} 
	dfs(root);          //從根節點開始遍歷
	cout<<max(dp[root][0],dp[root][1]);
	return 0;
} 

簡潔的結尾