树形DP

树的最长路径

1072. 树的最长路径

#include <cstring>
#include <iostream>
using namespace std;

const int N = 10010, M = N * 2;

int n;
// 邻接表存树，h[u] 存每个节点对应的链表，是相邻节点
int h[N], e[M], ne[M], w[M], idx;
int ans;

void add(int a, int b, int c) {
  e[idx] = b;
  w[idx] = c;
  ne[idx] = h[a];
  h[a] = idx++;
}

int dfs(int u, int father) {
  int dist = 0; // 表示从当前点往下走路径的的最大长度
  int d1 = 0, d2 = 0; // 树的直径对应从当前点往下走的所有路径中选一个权值最大和一个次大的
  // 依次考虑每个子节点
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    // 不要往上走
    if (j == father) continue;
    // 从子节点往下走路径的最大长度加上当前点到子节点的权值
    int d = dfs(j, u) + w[i];
    dist = max(dist, d);
    if (d >= d1)
      d2 = d1, d1 = d;
    else if (d > d2)
      d2 = d;
  }
  ans = max(ans, d1 + d2);
  return dist;
}

int main() {
  cin >> n;
  memset(h, -1, sizeof h);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c), add(b, a, c); // 无向图处理方式
  }
  dfs(1, -1);
  cout << ans << endl;
  return 0;
}

树的中心

1073. 树的中心

#include <cstring>
#include <iostream>
using namespace std;

const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;
int h[N], w[M], e[M], ne[M], idx;
int n;
int d1[N], d2[N], p1[N], up[N];
bool is_leaf[N];

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// 往下走，子节点更新父节点
int dfs_d(int u, int father) {
  d1[u] = d2[u] =
      -INF;  // 从节点 u 往下走的路径最大权值和次大权值，初始化为负无穷
  for (int i = h[u]; i != -1; i = ne[i]) {  // 遍历节点 u 的子节点
    int j = e[i];
    if (j == father) continue;
    int d =
        dfs_d(j, u) +
        w[i];  // 计算当前子节点往下走的路径最大值，再加上当前点到这个子节点的权值
    if (d >
        d1[u]) {  // 如果算出来的权值比当前存储的从 u 节点往下走的路径权值要大
      d2[u] = d1[u], d1[u] = d;  // 次大值更新，最大值更新
      p1[u] = j;  // 记录下取得最大值的路径，从 u 到哪个子节点
    } else if (d > d2[u])
      d2[u] = d;
  }
  if (d1[u] ==
      -INF) {  // 如果从节点 u 往下走的路径最大权值没被更新，说明 u 是叶子节点
    d1[u] = d2[u] = 0;
    is_leaf[u] = true;
  }
  return d1[u];
}

// 往上走，父节点更新子节点
void dfs_u(int u, int father) {
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    if (j == father) continue;
    if (p1[u] == j)
      up[j] = max(up[u], d2[u]) + w[i];
    else
      up[j] = max(up[u], d1[u]) + w[i];
    dfs_u(j, u);
  }
}

int main() {
  // 初始化邻接表
  memset(h, -1, sizeof h);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c), add(b, a, c);
  }
  dfs_d(1, -1);
  dfs_u(1, -1);
  int res = d1[1];
  for (int i = 2; i <= n; i++) {
    if (is_leaf[i])
      res = min(res, up[i]);
    else
      res = min(res, max(d1[i], up[i]));
  }
  printf("%d\n", res);
  return 0;
}

数字转换

1075. 数字转换

#include <cstring>
#include <iostream>

using namespace std;

const int N = 50010;

int n;
int h[N], e[N], ne[N], idx;
int sum[N];
bool st[N];
int ans;

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

int dfs(int u) {
  int d1 = 0, d2 = 0;
  for (int i = h[u]; i != -1; i = ne[i]) {
    int j = e[i];
    int d = dfs(j) + 1;
    if (d >= d1)
      d2 = d1, d1 = d;
    else if (d > d2)
      d2 = d;
  }
  ans = max(ans, d1 + d2);
  return d1;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j <= n / i; j++) {
      sum[i * j] += i;
    }
  }
  memset(h, -1, sizeof h);
  // 建树，并标记哪些不是树根
  for (int i = 2; i <= n; i++) {
    if (i > sum[i]) {
      add(sum[i], i);
      st[i] = true;
    }
  }
  // 遍历所有树根
  for (int i = 1; i <= n; i++) {
    if (!st[i]) {
      dfs(i);
    }
  }
  cout << ans << endl;
  return 0;
}

二叉苹果树

1074. 二叉苹果树

#include <cstring>
#include <iostream>

using namespace std;

const int N = 110, M = N * 2;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int f[N][N];

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int father) {
  for (int i = h[u]; ~i; i = ne[i]) {
    if (e[i] == father) continue;
    dfs(e[i], u);
    for (int j = m; j >= 0; j--) {
      for (int k = 0; k < j; k++) {
        f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);
      }
    }
  }
}

int main() {
  cin >> n >> m;
  memset(h, -1, sizeof h);
  for (int i = 0; i < n - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c), add(b, a, c);
  }
  dfs(1, -1);
  cout << f[1][m] << endl;
  return 0;
}

战略游戏

323. 战略游戏

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1510;

int n;
int h[N], e[N], ne[N], idx;
int f[N][2];
bool st[N];

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

void dfs(int u) {
  f[u][0] = 0;
  f[u][1] = 1;
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    dfs(j);
    f[u][0] += f[j][1];
    f[u][1] += min(f[j][0], f[j][1]);
  }
}
int main() {
  while (scanf("%d", &n) != -1) {
    memset(h, -1, sizeof h);
    idx = 0;
    memset(st, 0, sizeof st);
    for (int i = 0; i < n; i++) {
      int id, cnt;
      scanf("%d:(%d)", &id, &cnt);
      while (cnt--) {
        int ver;
        scanf("%d", &ver);
        add(id, ver);
        st[ver] = true;
      }
    }
    int root = 0;
    while (st[root]) root++;
    dfs(root);
    printf("%d\n", min(f[root][0], f[root][1]));
  }
  return 0;
}

皇宫看守树

1077. 皇宫看守

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1510;

int n;
int h[N], e[N], w[N], ne[N], idx;
int f[N][3];
bool st[N];

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

void dfs(int u) {
  f[u][2] = w[u];
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    dfs(j);
    f[u][0] += min(f[j][1], f[j][2]);
    f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
  }
  f[u][1] = 1e9;
  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));
  }
}

int main() {
  cin >> n;
  memset(h, -1, sizeof h);
  for (int i = 1; i <= n; i++) {
    int id, cost, cnt;
    cin >> id >> cost >> cnt;
    w[id] = cost;
    while (cnt--) {
      int ver;
      cin >> ver;
      add(id, ver);
      st[ver] = true;
    }
  }
  int root = 1;
  while (st[root]) root++;
  dfs(root);
  cout << min(f[root][1], f[root][2]) << endl;
  return 0;
}