感觉这并不是一道DP..

我是直接建了一个树,想想就过了。

首先我们以激发器来建一棵树

然后dfs找出每个点的深度

f[i]表示i点子树上叶节点的最大距离

在同一个分支,他的所有叶节点都必须要是相同的,而且不能减少

所以找出其中的最大值,其他的增加那么多

最后汇总到根节点就是最后的答案

#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;
}