原题传送门
这道题目可以放到普及T4难度
树型DP,记两个数组
d
p
[
u
]
dp[u]
dp[u]表示处理完自己为根的子树所需代价
l
e
n
[
u
]
len[u]
len[u]表示处理好自己的儿子后的最大深度
转移方程:
d
p
[
u
]
=
∑
d
p
[
v
]
+
∑
(
m
a
x
(
l
e
n
[
v
]
+
w
[
u
]
[
v
]
)
−
(
l
e
n
[
v
]
+
w
[
u
]
[
v
]
)
)
,
(
v
=
u
s
o
n
)
dp[u]=\sum_{}^{}dp[v]+\sum_{}^{}(max(len[v]+w[u][v])-(len[v]+w[u][v])),(v=u_{son})
dp[u]=∑dp[v]+∑(max(len[v]+w[u][v])−(len[v]+w[u][v])),(v=uson)
坑点是要开longlong,我因此wa了两发
Code:
#include <bits/stdc++.h>
#define maxn 1000010
#define LL long long
using namespace std;
struct Edge{
int to, next, len;
}edge[maxn << 1];
int num, head[maxn], n, r;
LL dp[maxn], len[maxn];
inline int read(){
int s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48) ;
return s * w;
}
void addedge(int x, int y, int z){ edge[++num] = (Edge) { y, head[x], z }; head[x] = num; }
void dfs(int u, int pre){
for (int i = head[u]; i; i = edge[i].next){
int v = edge[i].to;
if (v != pre){
dfs(v, u);
dp[u] += dp[v], len[u] = max(len[u], len[v] + edge[i].len);
}
}
for (int i = head[u]; i; i = edge[i].next){
int v = edge[i].to;
if (v != pre) dp[u] += len[u] - len[v] - edge[i].len;
}
}
int main(){
n = read(), r = read();
for (int i = 1; i < n; ++i){
int x = read(), y = read(), z = read();
addedge(x, y, z); addedge(y, x, z);
}
dfs(r, 0);
printf("%lld\n", dp[r]);
return 0;
}