CCPC-Wannafly Winter Camp Day1 (DIV2, Once) E flow flow (tree-shaped DP)

2023-01-23   ES  

algorithm Learning note: tree -shaped DP

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 n nPoints 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 f_{k,0/1} fk,0/1indicate nodes k k kand the maximum value and value of its child tree. 0 0 0indicate nodes k k kDon’t put it, 1 1 1indicate node k k kPut.

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

The calculation of f f fis 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,1u
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,0u
V}

among them V V VA collection of k k kson.

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 = ∅ U=\varnothing U=is also possible, so the answer may be 0 0 0

The last answer is

The maximum value in f r o o t , 0 / 1 f_{root,0/1} froot,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)

source

Related Posts

3.19 Machine Learning Application: Iris Category IRIS

Bootstrap Simple Time Control Bian

CIN.TIE and SyncwithStdio accelerate input and output

Keras starts from scratch to train a model that reaches 89%on CIFAR10

CCPC-Wannafly Winter Camp Day1 (DIV2, Once) E flow flow (tree-shaped DP)

Random Posts

CentOS7 adds hard disks to mount to/data directory

LOGSTASH nested json/multi -layer JSON parsing configuration configuration zhcha

linux file attributes of software and hard connection knowledge in depth explanation

Hibernate uses C3P0 database to connect pool spoke

jackson manual