题目描述
小 Q 在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字 1,2,3…进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。
在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信息，并将该激励电流传向与它连接并且尚未接收到激励电流的节点。最终，激烈电流将到达一些“终止节点”――接收激励电流之后不再转发的节点。
激励电流在导线上的传播是需要花费时间的，对于每条边 e，激励电流通过它需要的时间为 te ，而节点接收到激励电流后的转发可以认为是在瞬间完成的。现在这块电路板要求每一个“终止节点”同时得到激励电路――即保持时态同步。由于当前的构造并不符合时态同步的要求，故需要通过改变连接线的构造。目前小 Q有一个道具，使用一次该道具，可以使得激励电流通过某条连接导线的时间增加一个单位。请问小Q最少使用多少次道具才可使得所有的“终止节点”时态同步？
输入输出格式
输入格式：第一行包含一个正整数 N ，表示电路板中节点的个数。
第二行包含一个整数 S ，为该电路板的激发器的编号。
接下来 N−1行，每行三个整数 a,b,t。表示该条导线连接节点 a 与节点 b，且激励电流通过这条导线需要 t个单位时间。
输出格式：仅包含一个整数 V ，为小 Q最少使用的道具次数。
输入输出样例
3
1
1 2 1
1 3 3
2
说明
对于 40%的数据， N≤1000
对于 100%的数据， N≤500000
对于所有的数据， te≤1000000
Solution：
本题～不难～`～`。
我们随便画画图，很容易贪心的想到，最小的花费是长度最大的一条链，减去其它链的差的累加。
然后果断写，果然$WA$。（然而我并不知道为什么会有问题。）
后面发现，直接处理到根节点的链会出现重边（特别是可能多条链的直接父亲不一样），于是换个思路每次处理的是没有访问过的子树中最大的一条链长度$-$它的其它链的长度，有一点树形$dp$的意味。
最后遍历完整棵树，就能得到答案了。
代码：
#include<bits/stdc++.h> #define il inline #define ll long long #define Max(a,b) ((a)>(b)?(a):(b)) #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) using namespace std; const int N=1000005; int n,s,h[N],to[N],net[N],t[N],cnt; ll ans,maxn,p[N],tot; bool vis[N]; il int gi(){ int a=0;char x=getchar(); while(x<'0'||x>'9')x=getchar(); while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar(); return a; } il void add(int u,int v,int w){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,t[cnt]=w;} il void prepare(int x){ vis[x]=1; for(int i=h[x];i;i=net[i]) if(!vis[to[i]])prepare(to[i]),p[x]=Max(p[x],p[to[i]]+t[i]); } il void dfs(int x){ vis[x]=0; for(int i=h[x];i;i=net[i]) if(vis[to[i]])dfs(to[i]),ans+=p[x]-p[to[i]]-t[i]; } int main(){ n=gi(),s=gi(); int x,y,z; For(i,1,n-1){ x=gi(),y=gi(),z=gi(); add(x,y,z);add(y,x,z); } prepare(s); dfs(s); cout<<ans; return 0; }