传送门:https://www.luogu.org/problemnew/show/P1131
题目大意
给你一棵树,每条边有边权,要求增加一些边的边权,使得根节点到每个叶子节点的距离相等,求出最少共增加多少边权。
分析
简单树形DP,定义\(ans[u]\)表示根节点为\(u\)的最少边权,那么定义\(f[u]\)表示叶子中最大的距离,那么我们要将所有的其他路径都变成这个值,直接在当前状态下直接加掉。
ac代码
#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define N 500005
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; T fl = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') fl = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= fl;
}
struct edge {
int to, nt, w;
}E[N << 1];
ll ans[N], f[N];
int H[N];
int n, s, cnt;
void add_edge(int u, int v, int w) {
E[++ cnt] = (edge){v, H[u], w};
H[u] = cnt;
}
void dfs(int u, int fa) {
for (int e = H[u]; e; e = E[e].nt) {
int v = E[e].to;
if (v == fa) continue;
dfs(v, u);
f[u] = max(f[u], f[v] + E[e].w);
ans[u] += ans[v];
}
for (int e = H[u]; e; e = E[e].nt) {
int v = E[e].to;
if (v == fa) continue;
ans[u] += f[u] - f[v] - E[e].w;
}
}
int main() {
read(n); read(s);
for (int i = 1; i < n; i ++) {
int u, v, w;
read(u); read(v); read(w);
add_edge(u, v, w);
add_edge(v, u, w);
}
dfs(s, -1);
printf("%lld\n", ans[s]);
return 0;
}