# 2022 05 22 树形DP A

0.5h Anniversary party, POJ2342 提高 http://bailian.openjudge.cn/practice/2342
1h AtCoder Independent Set 提高 https://www.luogu.com.cn/problem/AT4537
1.5h CF1528A Parsa's Humongous Tree 提高 https://codeforces.com/problemset/problem/1528/A
0.5h Balancing Act, POJ1655 提高 http://bailian.openjudge.cn/practice/1655
0.5h Cow Marathon, POJ1985 提高 http://bailian.openjudge.cn/practice/1985

## Anneversary Party¶

$\begin{cases} dp[u, 1] = \sum dp[v, 0] \\ dp[u, 0] = \sum({\max(dp[v, 0], dp[v, 1])}) \end{cases}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6000 + 4;
int n, a[N], f[N][2];
int dp(int u, int s) {
int &d = f[u][s];
if (d > 0) return d;
if (s) d = a[u];
for (int v : adj[u]) d += s ? dp(v, 0) : max(dp(v, 1), dp(v, 0));
return d;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
int rt = 0;
for (int u, v; cin >> v >> u && u;) {
if (!rt || v == rt) rt = u;
}
if (!rt) rt = 1;
cout << max(dp(rt, 1), dp(rt, 0)) << endl;
return 0;
}

## Independent Set¶

$$dp[u,s]$$$$s=0/1$$ 表示黑/白色节点

$\begin{cases} dp[u, 0] = \prod_{v\in G(u)} dp[v, 0] + dp[v, 1] \\ dp[u, 1] = \prod_{v\in G(u)} dp[v, 1] \end{cases}$

/**
* @file atcoder/dp/p/main.cpp
* @brief
* @see https://atcoder.jp/contests/dp/submissions/32651189
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @date 2022/6/22 10:31:56
**/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N = 1e5 + 4, MOD = 1e9 + 7;
ll D[N][2];
vi G[N];
void dfs(int u, int fa) {
D[u][0] = 1, D[u][1] = 1;
for (int v : G[u]) {
if (v != fa) {
dfs(v, u);
D[u][0] *= (D[v][0] + D[v][1]) % MOD;
D[u][0] %= MOD;
D[u][1] *= D[v][0];
D[u][1] %= MOD;
}
}
}

int main() {
// High rating and good luck!
int n;
cin >> n;
for (int i = 0, u, v; i < n - 1; ++i) {
cin >> u >> v;
G[u].push_back(v), G[v].push_back(u);
}
dfs(1, -1);
cout << (D[1][0] + D[1][1]) % MOD << endl;
return 0;
}

## Balancing Act¶

$u.b = \max(\max_{v \in G(u)}(v.b), n-\sum_{v\in{G(u)}}v.b)$
#include <bits/stdc++.h>
const int NN = 20000 + 4;
using namespace std;
int N, MaxS, Centroid;
vector<int> G[NN];
int dfs(int u, int fa) {
int s = 1, max_s = -1;
for (int v : G[u]) {
if (v == fa) continue;
int sv = dfs(v, u);
s += sv, max_s = max(max_s, sv);
}
max_s = max(max_s, N - s);
if (max_s < MaxS || (max_s == MaxS && Centroid > u))
MaxS = max_s, Centroid = u;
return s;
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> N;
for (int i = 1; i <= N; i++) G[i].clear();
for (int i = 1, u, v; i < N; i++)
cin >> u >> v, G[u].push_back(v), G[v].push_back(u);
MaxS = NN, Centroid = 0, dfs(1, -1);
printf("%d %d\n", Centroid, MaxS);
}
return 0;
}

## Cow Marathon¶

/**
* @file poj/1985/main.cpp
* @brief
* @see
* @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
* @date 2022/6/23 13:06:23
**/

#include <bits/stdc++.h>
const int N = 1e6 + 4;
struct Edge {
int v, w;
};
using namespace std;
int n, m, ans, D[N];
void dfs(int u, int fa) {
int &d = D[u], d1 = 0;  // 最短路长度，次短路长度
d = 0;
for (const auto& [v, w] : adj[u]) {
if (v == fa) continue;
dfs(v, u);
int nd = w + D[v];
if (nd > d)
d1 = d, d = nd;
else if (d > d1)
d1 = nd;
}
ans = max(ans, d + d1);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
string S;
cin >> u >> v >> w >> S;
}