传送门
分析
系统的刷一下换根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;
}