P1131 [ZJOI2007]时态同步（树形DP）

题目

luogu1131

题解

设$dis[i]$表示在以$i$为根的子树中，叶子节点到$i$的最大距离统计时令$u$为父亲节点，$v$为叶子节点，答案$ans+=dis[u]-(dis[v]+dis(u,v))$

code

#include <map> #include <set> #include <list> #include <cmath> #include <deque> #include <stack> #include <queue> #include <cstdio> #include <cctype> #include <vector> #include <string> #include <cstring> #include <iomanip> #include <complex> #include <iostream> #include <algorithm> #include <functional> using namespace std; typedef long long LL; const int maxn = 500000 + 100; const int inf = 0x3f3f3f3f; template <class T> inline void read(T &s) { s = 0; T w = 1, ch = getchar(); while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); } while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); } s *= w; } LL ans; LL dis[maxn]; int n, s, tot; int lin[maxn]; struct Edge { int next, to, dis; } e[maxn * 2]; inline void add(int from, int to, int dis) { e[++tot].to = to; e[tot].dis = dis; e[tot].next = lin[from]; lin[from] = tot; } void dfs(int u, int fa) { for (int i = lin[u]; i; i = e[i].next) { int v = e[i].to; if (v == fa) continue; dfs(v, u); dis[u] = max(dis[u], dis[v] + e[i].dis); } for (int i = lin[u]; i; i = e[i].next) { int v = e[i].to; if (v == fa) continue; ans += dis[u] - (dis[v] + e[i].dis); } } int main() { read(n); read(s); for (int i = 1; i < n; ++i) { int u, v, w; read(u), read(v), read(w); add(u, v, w); add(v, u, w); } ans = 0ll; dfs(s, 0); printf("%lld\n", ans); return 0; }