换根 DP 学习笔记

前言

没脑子选手什么都不会。

正文

先来写一下换根 DP 的特点或应用方面：

不同的点作为树的根节点，答案不一样。
求解答案时要求出每一个节点的信息。
无法通过一次搜索完成答案的求解，因为一次搜索只能得到一个节点的答案。

下面来看一个例子：

给定一个 \(n\) 个点的无根树，问以树上哪个节点为根时，其所有节点的深度和最大。

一个显然的做法：枚举根节点然后 \(O(n)\) 暴力，复杂度 \(O(n^2)\) 。能过我 CS

所以我们考虑换根 DP 。

先以 \(1\) 节点为根节点算出每个点的深度 \(deep_i\) 和每个点为根的子树大小 \(siz_i\)
那么此时我们就知道了 \(1\) 为根节点时的答案 \(ans_1=\sum deep_i\) 。
接下来我们来看第二遍 \(\text{dfs}\) ，考虑如何由 \(ans_1\) 转换到 \(ans_i\) 。
因为还是从 \(1\) 节点开始向下遍历，所以默认 \(t\) 是 \(u\) 的孩子节点。
很显然，转移的时候把树分成两个块：1.本来就是 \(t\) 的子树 2. 原来不是 \(t\) 的子树。
先来考虑原来就是 \(t\) 子树的情况：每一个节点的值都要减一，所以 ans -= siz[t]
在来考虑另一种情况：每个节点显然答案加一，所以 ans += n - siz[t]

\[ans_t=ans_u+n-2\times siz_t
\]

Code

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

#define file(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

#define Enter putchar('\n')

#define quad putchar(' ')

#define int long long

const int N = 1000005;

int n, deep[N], siz[N], f[N];

std::vector <int> dis[N];

inline void dfs1(int now, int father) {

  deep[now] = deep[father] + 1;

  siz[now] = 1;

  for (int t : dis[now]) {

    if (t == father) continue;

    dfs1(t, now);

    siz[now] += siz[t];

  }

}

inline void dfs2(int now, int father) {

  for (int t : dis[now]) {

    if (t == father) continue;

    f[t] = f[now] + n - 2 * siz[t];

    dfs2(t, now);

  }

}

signed main(void) {

  // file("P3478");

  std::ios::sync_with_stdio(false);

  std::cin.tie(0);

  std::cout.tie(0);

  std::cin >> n;

  for (int i = 1, x, y; i < n; i++) {

    std::cin >> x >> y;

    dis[x].emplace_back(y);

    dis[y].emplace_back(x);

  }

  dfs1(1, 0);

  for (int i = 1; i <= n; i++)

    f[1] += deep[i];

  dfs2(1, 0);

  int ans = 0, out;

  for (int i = 1; i <= n; i++) {

    if (f[i] > ans) {

      ans = f[i];

      out = i;

    }

  }

  std::cout << out << std::endl;

  return 0;

}

所以我们可以发现：

换根 DP 一般都是先选择任意一个点为根节点预处理出一些有用的信息。

然后第二遍 dfs 时再根据已知的答案推出其他节点的答案。

巴特西

换根 DP 学习笔记

前言

正文

Code

最新文章

热门文章