# 感觉这并不是一道DP..
## 我是直接建了一个树,想想就过了。
首先我们以激发器来建一棵树
然后dfs找出每个点的深度
f[i]表示i点子树上叶节点的最大距离
在同一个分支,他的所有叶节点都必须要是**相同**的,而且**不能减少**
所以找出其中的最大值,其他的增加那么多
最后汇总到根节点就是最后的答案
```cpp
#include<cstdio>
#define fmax(a,b) ((a)>(b)?(a):(b))
struct edge{
long long from,to,dis;
long long next;
}e[1000010];
long long n,s,len,ans,vis[500010],f[500010],head[500010];
long long v_in(){
long long sum=0;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9'){
sum=sum*10+ch-'0';
ch=getchar();
}
return sum;
}
void add(long long u,long long v,long long w){//加边处理
e[++len].from=u;
e[len].to=v;
e[len].dis=w;
e[len].next=head[u];
head[u]=len;
}
void dfs1(long long u){
vis[u]=1;
for (long long i=head[u];i!=0;i=e[i].next){
long long v=e[i].to;
if (vis[v]==0){
dfs1(v);
f[u]=fmax(f[u],f[v]+e[i].dis);//深搜距离
}
}
}
void dfs2(long long u){
vis[u]=1;
for (long long i=head[u];i!=0;i=e[i].next){
long long v=e[i].to;
if (vis[v]==0){
dfs2(v);
ans+=f[u]-f[v]-e[i].dis;//我们要保证每棵子树的所有叶子节点到该点的距离相等,所以必须将他们都修改到最大值
}
}
}
int main(){
n=v_in();
s=v_in();
for (long long i=1;i<n;i++){
long long u=v_in(),v=v_in(),w=v_in();//读入边,加无向边
add(u,v,w);
add(v,u,w);
}
dfs1(s);//第一遍深搜找出每个点子树距离最大值
for (int i=1;i<=n;i++) vis[i]=0;
dfs2(s);//第二遍深搜找出需要使用的最小值
printf("%lld\n",ans);
return 0;
}
```