题目传送门(BZOJ)
>原文链接<

题解 :

状态 :$F[p]$为点$p$到自己的所有叶子的最长时间。

转移 :$F[p] = \max{F[to[i]]+val[i]}$

在求得每个点的$F$之后,再把$\sum(F[p]-F[to[i] – val[i])$累加在答案上即可。

非常简单的树形DP

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 1001010;long long f[N];struct Edge { int to, val; Edge *next;}*h[N], e[N<<1];int _;inline char Nc() { static char Buf[100000], *p1, *p2; return p1==p2&&(p2=(p1=Buf)+fread(Buf, 1, 100000, stdin), p1==p2)?EOF:*p1++;}int Rd() { int x = 0;char c = Nc(); while(!isdigit(c)) c=Nc(); while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=Nc(); return x;}void Add_Edge(int u, int v, int w) { Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp; tmp = &e[++_]; tmp->to = u; tmp->val = w; tmp->next = h[v]; h[v] = tmp;}long long ans = 0;void Dfs1(int p, int fa) { long long now = 0; for(Edge *i = h[p]; i; i = i->next) { if(i->to!=fa) { Dfs1(i->to, p); now = max(now, f[i->to]+i->val); } } f[p] = now; for(Edge *i = h[p]; i; i = i->next) { if(i->to!=fa) { ans += now-(f[i->to]+i->val); } }}int main() { int n = Rd(), s = Rd(); for(int i = 2; i <= n; i ++ ) { int u = Rd(), v = Rd(), w = Rd(); Add_Edge(u, v, w); } Dfs1(s, 0); printf("%lld\n", ans);}