?
1. Concept introduction
Tree DP is dynamic programming based on trees as a model. Mainly use the substructure brought by the tree itself (the parent-child relationship on the tree) to perform state transfer. Generally, the DP value of the parent node is derived from the DP value of the child node.
2. Detailed explanation of examples
Without further ado, let’s look directly at the examples:
2.1 Dance without a boss
Title link: Dance without a boss
2.1.1 Question Analysis
The return value of tree dp is definitely related to root.
We can construct the meaning of each dimension of the tree dp based on the solution to the knapsack problem.
dp[root][0]: subtree with root as the root node, the current root node does not come
dp[root][1]: subtree with root as the root node, the current root node comes from
State transition equation: (where u is a child node of v)
d
p
[
u
]
[
0
]
=
Σ
m
a
x
(
d
p
[
v
]
[
0
]
,
d
p
[
v
]
[
1
]
)
,
v
yes
u
child nodes of
dp[u][0]=Σmax(dp[v][0],dp[v][1]), v is a child node of u
dp[u][0]=Σmax(dp[v][0],dp[v][1]), v is a child node of u
d
p
[
u
]
[
1
]
=
h
a
p
p
y
[
u
]
+
Σ
d
p
[
v
]
[
0
]
,
v
yes
u
child nodes of
dp[u][1]=happy[u] + Σdp[v][0], v is a child node of u
dp[u][1]=happy[u] + Σdp[v][0], v is a child node of u
State initial value: The initial value is at the leaf node and does not require manual initialization.
2.1.2 Code
#include<bits/stdc + + .h>
using namespace std;
#define endl '\
'
#define int long long
#define For(i, a, b) for(int i = a;i <= b;i + + )
typedef pair<int, int> PII;
const int N = 1e4;
vector<int> adj[N];
int happy[N], in[N], n, dp[N][2];
void dfs(int u){
dp[u][1] = happy[u];
for (int v: adj[u]){
dfs(v);
dp[u][1] + = dp[v][0];
dp[u][0] + = max(dp[v][0], dp[v][1]);
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
For (i, 1, n){
cin >> happy[i];
}
For (i, 1, n - 1){
int u, v;
cin >> u >> v;
adj[v].push_back(u);
in[u] + + ;
}
int root = 1;
while (in[root])
root++;
dfs(root);
cout << max(dp[root][0], dp[root][1]) << endl;
return 0;
}
2.2 Course selection
2.2.1 Question Analysis
Since this is a forest, we need to build a super origin.
If we simply consider dynamic programming from the perspective of a tree, assuming that the maximum score obtained by selecting j courses from the tree with i as the root node is f (i, j), assuming that the virtual tree root number is 0 and the credit is 0, then , ans = f (0, n + 1)
If the tree root chooses 1 homework, the remaining j – 1 homework becomes a problem of how to allocate resources to all his sons. This is obviously a knapsack problem.
Assume that the optimal value of x courses taken by the first k sons is g(k, x), then there is:
g
(
k
,
x
)
=
max
?
=
{
g
(
k
?
1
,
x
)
No.
k
My son does not take elective courses
g
(
k
?
1
,
x
?
y
)
+
g
(
s
o
n
(
k
)
,
y
?
1
)
+
a
[
k
]
No.
k
son elective
y
Door
here
s
o
n
(
k
)
Refer to
k
the number of children of a node
g(k,x)=\max=\left\{ \begin{aligned} & amp;g(k-1,x) & amp; & amp;The k-th son does not take electives\cr & amp;g(k -1,x-y) + g(son(k),y-1) + a[k] & The number of sons\end{aligned} \right.
g(k,x)=max=?
in:
0
≤
x
≤
j
?
1
,
a
n
s
=
g
(
s
o
n
(
0
)
,
n
+
1
)
Among them: 0≤x≤j?1,ans=g(son(0),n + 1)
Among them: 0≤x≤j?1,ans=g(son(0),n + 1)
2.2.2 Code
#include<bits/stdc + + .h>
using namespace std;
#define endl '\
'
#define int long long
#define For(i, a, b) for(int i = a;i <= b;i + + )
typedef pair<int, int> PII;
const int N = 400;
int n, m, w[N], dp[N][N];
vector<int> adj[N];
void dfs(int u){
for (int v: adj[u]){
dfs(v);
for (int tot = m; tot >= 0;tot--){
For (j, 1, tot){
dp[u][tot] = max(dp[u][tot], dp[u][tot - j] + dp[v][j]);
}
}
}
for (int i = m; i > 0;i--){
dp[u][i] = dp[u][i - 1] + w[u];
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i + + ){
int u, x;
cin >> u >> x;
adj[u].push_back(i);
w[i] = x;
}
m + = 1;
dfs(0);
cout << dp[0][m];
return 0;
}
3. Conclusion
That’s it for today’s content, I will return to qwq for the third time in a row.
?