头一次看到这道题的时候被题面吓到了......因为我焊电路板的时候全是毛刺XD
我写的方法是类似于贪心，看到Luogu上好多大佬写树上DP......orz
题意简述：
给定一颗边权为非负整数的树，通过增加（只能增加）一些边的边权，使根节点到每个叶节点的路径上的边权和相等，在此基础上，求最小的边权和该变量。
思路：
首先可以看出来，如果某几条边分别都要增加一个量，而这些边又都是从同一个公共父节点发出来的，那么不如把这个增加量转移到它们公共父节点的边上。
这样就可以将许多变化量集中为一个，层层向上推得出最优解。
如下图：
所以：
首先预处理，找出所有子节点中离根节点最远的那一个，记录其距离为 $ maxn $ ，作为所有节点的目标距离。
然后，对于每一个叶节点 $ x $ ，连接它和它的父节点之间那条边的增加量即为 $ maxn-dis[x] $ ，即所要增加的差值。
在DFS过程中，对于某个节点 $ x $ ：
设 $ v $ 为 $ x $ 的子节点
设连接 $ v $ 与 为 $ x $ 的边为 $ S $
设 $ ad[v] $ 为S期望的增加量
则有：
$ ad[x]=Σ_v min(ad[x],ad[v]) $
即：找出所有通向儿子的边中，最小的增加量，将这份增加量转移到父节点和（父节点的父节点）之间的边上。
同时还要把所有通向儿子的边的增加量，减去这个转移走的量。
最后答案就是整个图中，所有边增加量的总和。
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
int n,s;
int out[500050];
int u[500050],v[500050],w[500050],head[500050],nxt[500050],cnt=0;
void add(int ui,int vi,int wi){
cnt++;
nxt[cnt]=head[ui];
head[ui]=cnt;
u[cnt]=ui;
v[cnt]=vi;
w[cnt]=wi;
}
LL d[500050];
LL maxn=0;
void init(int ui,int fa){
for(int i(head[ui]);i;i=nxt[i]){
int vi=v[i];
int wi=w[i];
if(vi==fa)continue;
d[vi]=d[ui]+wi;
maxn=max(maxn,d[vi]);
init(vi,ui);
}
}
LL ad[500050];
void dfs(int ui,int fa){
for(int i(head[ui]);i;i=nxt[i]){
int vi=v[i];
int wi=w[i];
if(vi==fa)continue;
dfs(vi,ui);
if(i==head[ui])ad[ui]=ad[vi];
ad[ui]=min(ad[ui],ad[vi]);
}
if(ui==s)return;
//printf("ad[%d]=%d
",ui,ad[ui]);
for(int i(head[ui]);i;i=nxt[i]){
int vi=v[i];
if(vi==fa)continue;
ad[vi]-=ad[ui];
//printf("ad[%d]-=ad[%d]
",vi,ui);
}
}
int main(){
scanf("%d%d",&n,&s);
for(int i(1);i<=n-1;i++){
int ui,vi,wi;scanf("%d%d%d",&ui,&vi,&wi);
add(ui,vi,wi);
add(vi,ui,wi);
out[ui]++;
out[vi]++;
}
init(s,0);
for(int i(1);i<=n;i++){
if(out[i]==1){
ad[i]=maxn-d[i];
continue;
}
d[i]=0;
}
LL ans=0;
dfs(s,0);
for(int i(1);i<=n;i++)ans+=ad[i];
printf("%lld",ans);
return 0;
}