系统的刷一下换根DP这个专题
首先如果我们固定一个根节点的话,可以在
O
(
n
)
O(n)
O(n)的复杂度内解决这个问题,但这道题是不定根,如果我们去一次枚举根的话,显然
O
(
n
2
)
O(n ^ 2)
O(n2)的复杂度是不合适的,那么我们怎么去优化呢
假设我们先
d
f
s
dfs
dfs一下这个棵树,假设根为
r
o
o
t
root
root,处理出
d
i
d_{i}
di数组表示以
i
i
i为根节点的子树中的最大流量是多少,那么以
r
o
o
t
root
root为根的答案就为
f
[
r
o
o
t
]
=
d
[
r
o
o
t
]
f[root] = d[root]
f[root]=d[root],然后再
d
f
s
dfs
dfs一下这棵树,
r
o
o
t
root
root的子节点
j
j
j的答案,就是以子节点
j
j
j构成的子树
d
i
d_{i}
di再加上流向父节点的流量,处理一下即可
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #define dl(x) printf("%lld\n",x); #define di(x) printf("%d\n",x); using namespace std; const int N = 1e6 + 10; template<typename T>inline void read(T &a) { char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();} while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x; } int h[N], e[N], ne[N], w[N], idx; int n, d[N], in[N], f[N]; void init() { for (int i = 1; i <= n; i++) h[i] = -1, in[i] = 0; idx = 0; } void add(int x, int y, int z) { ne[idx] = h[x], e[idx] = y, w[idx] = z, h[x] = idx++; } void dfs(int u, int fa) { d[u] = 0; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dfs(j, u); if (in[j] == 1) d[u] += w[i]; else d[u] += min(w[i], d[j]); } } void dfs_(int u, int fa) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; if (in[u] == 1) f[j] = d[j] + w[i]; else f[j] = d[j] + min(f[u] - min(d[j], w[i]), w[i]); dfs_(j,u); } } int main() { int T; read(T); while (T--) { read(n); init(); for (int i = 1; i < n; i++) { int x, y, z; read(x), read(y), read(z); add(x, y, z), add(y, x, z); in[x]++, in[y]++; } dfs(1, -1); f[1] = d[1]; dfs_(1, -1); int res = 0; for (int i = 1; i <= n; i++) res = max(res, f[i]); di(res); } return 0; }