每日一题：Accumulation Degree

题意

给定一棵n个节点的树，边权值视作流量，找到一个源点使得从该点出发到所有叶子节点流量和最大。

思路：

我们先考虑这样一道题：指定一点使得到树上其他点的深度之和最小。

这显然是树的重心的性质：树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。

我们先假设这棵树的根为1，进行一次dfs，可以求出每个点的深度 $dep[i]$ 和子树大小 $size[i]$ ，设某点作为根深度之和为 $f$( i )，显然：$f(1)$ = $\sum_{i=1}^{n}{dep[i]}$。

当根从 $u$ 转移到子节点 $v$ 时，以 $v$ 为根的子树内所有节点 $dep$ 都减1，其余节点加1。从而得到状态转移方程：$f[v] = f[u] - size[v] + (n - size[v]) = f[u] + n - 2 * size[v]$，答案取最小值即可，时间复杂度 $O (n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e6 + 5;

int n, res, idx, h[N], dep[N], size[N];
long long f[N];

struct Node {
  int to, next;
} E[N];

void add(int a, int b) { E[idx].to = b, E[idx].next = h[a], h[a] = idx++; }

void dfs1(int u, int fa) {
  size[u] = 1;
  dep[u] = dep[fa] + 1;
  for (int i = h[u]; ~i; i = E[i].next) {
    int v = E[i].to;
    if (v == fa) continue;
    dfs1(v, u);
    size[u] += size[v];
  }
}

void dfs2(int u, int fa) {
  for (int i = h[u]; ~i; i = E[i].next) {
    int v = E[i].to;
    if (v == fa) continue;
    f[v] = f[u] + n - 2LL * size[v];
    dfs2(v, u);
  }
}

int main() {
  memset(h, -1, sizeof(h));
  cin >> n;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    add(x, y);
    add(y, x);
  }
  dep[0] = -1;
  dfs1(1, 0);
  for (int i = 1; i <= n; i++) f[1] += dep[i];
  dfs2(1, 0);
  long long sum = 0x3ffffffffffff;
  for (int i = 1; i <= n; i++) {
    if (sum > f[i]) {
      sum = f[i];
      res = i;
    }
  }
  cout << sum << '\n';
  return 0;
}

现在我们回过头来看这道题，可以发现思路都大同小异，只是转移方程发生了变化。

定义 $flow[i]表示以 i 为根的子树中流量的最大值$，那么，当节点从 $u$ 转移到 $v$ 时，我们可以得到：

1. 当 $v$ 为叶子结点，则 $flow[u] += flow[v]$ ；
2. 当 $u$ 为非叶子结点，则 $flow[u] = min(flow[v], fl(u, v))$ $(fl(u, v) 即u, v两点间的流量限制)$ 。

这样，根为1时的 $flow[1]$ 就求出来了。

接下来考虑根节点的转移：从以 $u$ 为根节点转移为以 $v$ 为根节点，对于根节点 $v$ 而言，唯一会产生影响的就是 $v$ 流向 $u$ 的路径，也就是对于换根后所有用到这条边的路径，都要加上这条流量的限制，则状态转移方程为：

1. 当 $u$ 为叶子节点时，$f[v] += fl(u, v)$ ;
2. 当 $v$ 为非叶子结点时，$f[v] += min(fl(u, v), flow[u] - min(flow[v], fl(u, v)))$ 。

进行两次dfs即可，时间复杂度 $O(n)$。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int t, n, res, idx, h[N], d[N], f[N];

struct Node {
  int to, w, next;
} E[N << 1];

void add(int a, int b, int c) {
  E[idx].to = b, E[idx].w = c, E[idx].next = h[a], h[a] = idx++;
}

void dfs1(int u, int fa) {
  for (int i = h[u]; ~i; i = E[i].next) {
    int v = E[i].to, w = E[i].w;
    if (v == fa) continue;
    dfs1(v, u);
    if (d[v] == 1)
      f[u] += w;
    else
      f[u] += min(f[v], w);
  }
}

void dfs2(int u, int fa) {
  for (int i = h[u]; ~i; i = E[i].next) {
    int v = E[i].to, w = E[i].w;
    if (v == fa) continue;
    if (d[u] == 1)
      f[v] += w;
    else
      f[v] += min(w, f[u] - min(f[v], w));
    dfs2(v, u);
  }
}

int main() {
  cin >> t;
  while (t--) {
    idx = 0;
    memset(h, -1, sizeof(h));
    memset(d, 0, sizeof(d));
    memset(f, 0, sizeof(f));
    cin >> n;
    for (int i = 1; i < n; i++) {
      int x, y, z;
      cin >> x >> y >> z;
      add(x, y, z);
      add(y, x, z);
      d[x]++;
      d[y]++;
    }
    dfs1(1, 0);
    dfs2(1, 0);
    res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res << '\n';
  }
  return 0;
}

总结

对于换根dp，一般有两个步骤：

1. 默认1为根进行dfs预处理；
2. 从1开始，进行根的转移，计算贡献变化。

对于dp而言，状态转移方程是最重要的，需要多思考，多刷题，才能累积经验，掌握要点。