tree -shaped DP, a dp(nonsense), dedicated to DP on the tree.

This type of DP is very easy to understand because of its panels.

and tree -shaped DP do not look like DP, more like violent search.

Example:P1352 No Boss Dance

Topic is actually given a tree$n$Points of the trees, choose some points, so that these points are not adjacent to each other, and the maximum point of power is required.

This is the topic of the tree DP.

First save the tree.

Foreword says that the tree -shaped DP is more like a violent search, so we need to make DFS again on this tree, while DFS DP.

Considering that tree DP is a DP(Isn’t it), so we still need the basic routine of DP: set the state, push the transition equation, push the initial value, and ask for the answer.

All discussions below

assume that the shape and root of the tree have been determined.

$f_{k,0/1}$indicate nodes$k$and the maximum value and value of its child tree.$0$indicate nodes$k$Don’t put it,$1$indicate node$k$Put.

So as a tree -shaped DP, it is very important:Father Node

The calculation of$f$is related to the child node.

Therefore, for this question, our state transfer equation is as follows:

f k , 0 = max ⁡ { f u , 0 , f u , 1 ∣ u ∈ V } f_{k,0}=\max\{f_{u,0},f_{u,1} | u \in V\} fk,0​=max{
fu,0​,fu,1​∣u∈V}

f k , 1 = r k + max ⁡ { f u , 0 ∣ u ∈ V } f_{k,1}=r_k+\max\{f_{u,0} | u \in V\} fk,1​=rk​+max{
fu,0​∣u∈V}

among them$V$A collection of$k$son.

If this point is not selected, the son can choose or not; but if you choose, the son cannot choose.

Note: Selected point sets$U=\varnothing$is also possible, so the answer may be$0$。

The last answer is

The maximum value in$f_{root,0/1}$.

code:

#include <bits/stdc++.h>
#define Max(a, b) ((a > b) ? a : b)
using namespace std;

typedef long long LL;
const int MAXN = 6e3 + 10;
int n, r[MAXN], f[MAXN][2], root;
vector <int> Next[MAXN];
bool book[MAXN];

int read()
{
    
	int sum = 0, fh = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
	return sum * fh;
}

void dfs(int now, int fa)
{
    
	f[now][0] = 0, f[now][1] = r[now];
	for (int i = 0; i < Next[now].size(); ++i)
	{
    
		int u = Next[now][i];
		if (u == fa) continue;
		dfs(u, now);
		f[now][0] = Max(f[now][0], Max(f[now][0] + f[u][0], f[now][0] + f[u][1]));
		f[now][1] = Max(f[now][1], f[now][1] + f[u][0]);
	}
}

int main()
{
    
	n = read();
	for (int i = 1; i <= n; ++i) r[i] = read();
	for (int i = 1; i < n; ++i)
	{
    
		int x = read(), y = read(); book[x] = 1;
		Next[y].push_back(x); Next[x].push_back(y);
	}
	for (int i = 1; i <= n; ++i)
		if (!book[i]) {
    root = i; break;}
	dfs(root, root);
	printf("%d\n", Max(f[root][0], f[root][1]));
	return 0;
}

Here provides a tree -shaped DP board,But it cannot guarantee that this board can pass all the topics.

int f[...];

void dfs(int now, int fa...)
{
    
	/*Set the initial value* /
	for (/*Like the son* /)
	{
    
		int u = /*Son* /;
		if (u == fa) continue;// Be careful not to return to the father node
		dfs(u, now...);
		/*Moved* /
	}
}

Practice Title Transmitting Door:DP algorithm summary & special training 2 (tree -shaped DP)