JZTXT

换根DP

发布时间 2023-05-28 10:41:48作者: SunnyYuan

换根法思路：

  1. 自下而上递推；
  2. 自上而下递推。

P3478 [POI2008] STA-Station

首先使用 \(\text{dfs}\) 求出以每个节点 \(u\) 为根的子树大小 \(s[u]\)。

然后我们设 \(f[i]\) 为以 \(i\) 为根时所有节点的深度之和，\(j\) 为 \(i\) 的子节点。

那么对于所有 \(j\) 的子节点，深度都减 \(1\)，所以总共减少了 \(s[j]\)。

对于所有不是 \(j\) 的子节点的节点，深度都加 \(1\) ，所以总共加了 \(n - s[j]\)。

所以 \(f[j] = f[i] - s[j] + n - s[j] = f[i] + n - 2 \times s[j]\)。

最后取 \(\max\) 即可。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using i64 = long long;

const int N = 1000010;

struct Edge {
	int to, next;
}e[N * 2];

int head[N], idx;

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

int n;
int sz[N];

void dfs1(int u, int fa) {
	sz[u] = 1;
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == fa) continue;
		dfs1(to, u);
		sz[u] += sz[to];
	}
}

int f[N];
int maxv, ans;

void dfs2(int u, int fa) {
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == fa) continue;
		f[to] = f[u] + n - 2 * sz[to];
		dfs2(to, u);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	dfs1(1, 0);
	for (int i = 1; i <= n; i++) f[1] += sz[i];
	dfs2(1, 0);
	for (int i = 1; i <= n; i++) if (f[i] > maxv) maxv = f[i], ans = i;
	cout << ans << '\n';
	return 0;
}

AcWing 287. 积蓄程度 / POJ 3585 Accumulation Degree

设 \(d[i]\) 表示 \(i\) 点可以向下传递的最大流量。

设 \(f[i]\) 表示 \(i\) 点可以向外传递的最大流量（包括向下流的流量和向上流的流量）。

先 \(\text{dfs}\) 一遍求出 \(d\)。

有：

如无特殊说明 \(to\) 表示 \(i\) 的子节点，\(edge(i, to)\) 表示 \(i\) 和 \(to\) 这条边的最大流量。

\(d[i] = \sum \min(d[to], edge(i, to))\)

\(f[to] = \min(edge(i, to), f[i] - \min(edge(i, to), d[to]))\)

同时注意如果根的度为 \(1\)（如下图） ，那么计算它的子节点时要采用公式：

\(f[i] = f[to] + edge(i, to)\)

image

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;

struct Edge {
	int to;
	int next;
	int w;
}e[N * 2];

int head[N], idx, deg[N];

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

int n;
int f[N], d[N];

int dfs1(int u, int fa) {
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == fa) continue;
		d[u] += min(dfs1(to, u), e[i].w);
	}
	if (deg[u] == 1) return INF;
	return d[u];
}

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

void solve() {
	idx = 0;
	memset(head, 0, sizeof(head));
	memset(deg, 0, sizeof(deg));
	memset(f, 0, sizeof(f));
	memset(d, 0, sizeof(d));
	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);
		deg[x]++;
		deg[y]++;
	}
	dfs1(1, 0);
	f[1] = d[1];
	dfs2(1, 0);
	int ans = 0;
	for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin >> T;
	while (T--) solve();

	return 0;
}