傳送門：https://www.luogu.org/problemnew/show/P1131

題目大意

給你一棵樹，每條邊有邊權，要求增加一些邊的邊權，使得根節(jié)點到每個葉子節(jié)點的距離相等，求出最少共增加多少邊權。

分析

簡單樹形DP，定義\(ans[u]\)表示根節(jié)點為\(u\)的最少邊權，那么定義\(f[u]\)表示葉子中最大的距離，那么我們要將所有的其他路徑都變成這個值，直接在當前狀態(tài)下直接加掉。

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; }

轉載于:https://www.cnblogs.com/chhokmah/p/10552094.html

總結

以上是生活随笔為你收集整理的[luogu1131][bzoj1060][ZJOI2007]时态同步【树形DP】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。