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¶

又名：没有上司的舞会

状态：\(dp[u, s]\) 为子树 \(u\) 选择状态 \(s\) 对应子树的快乐度最大值，\(s=1\) 表示这个人参会，\(s=0\) 表示这个人不参会

转移：

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

时间复杂度：\(O(N)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6000 + 4;
vector<int> adj[N];
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;) {
    adj[u].push_back(v);
    if (!rt || v == rt) rt = u;
  }
  if (!rt) rt = 1;
  cout << max(dp(rt, 1), dp(rt, 0)) << endl;
  return 0;
}

Independent Set¶

给定一棵树，可以将节点染成黑色或白色，但相邻两个节点不能同时是黑色，求方案数 \(\pmod{10^9+7}\)

\(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} \]

实现时注意题目给定的是无向图，双向加边后 dfs 即可。

/**
 * @file atcoder/dp/p/main.cpp
 * @brief
 * @see https://atcoder.jp/contests/dp/submissions/32651189
 * @author Ruiming Guo (guoruiming@stu.scu.edu.cn)
 * @copyright 2022
 * @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\)作为根节点，\(d(u)\) 表示以 \(u\) 为根的子树的结点个数，\(u.b\) 表示 \(u\) 点的平衡度

\[ 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)
 * @copyright 2022
 * @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];
vector<Edge> adj[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;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  ans = -1;
  dfs(1, -1);
  cout << ans << endl;
}