从前有一棵修炼成仙的橙子树，树上结满来，任意两个值最低为多少。 护法不需要回到最开始召唤他的位置（只需吃掉所有的橙子）。

Question

从前有一棵修炼成仙的橙子树，树上结满了神奇的橙子，只要吃了一枚就能 +1s。为了防止有刁民来偷吃橙子，树神就想召唤一名护法把橙子树上的所有橙 子都吃了，这样就没有人能偷走橙子啦。 橙子树上有 n 枚橙子，编号为 1~n，由 n-1 条树枝全部连起来，任意两个橙 子之间有且只有一条路径（由树枝组成的路径）相连，最开始时树神会选择其中 一枚橙子位置的编号 s 召唤一名护法并从这个位置开始吃，并且护法只能沿着树 枝移动，由于每条树枝的长度不同，而护法移动距离之和等于树神消耗的法力值， 树神想知道，让护法吃掉所有橙子所消耗的法力值最低为多少。 护法不需要回到最开始召唤他的位置（只需吃掉所有的橙子）。 ★数据输入 输入第一行为两个正整数 n 和 s，n 表示橙子的数量，s 表示召唤护法的起始 位置编号。 接下来 n-1 行，每行三个整数 u，v，w（w<=1000），表示编号为 u 和 v 的橙 子之间由一条长度为 w 的树枝直接相连。 30%的数据：n<=500； 60%的数据：n<=1000； 100%的数据：n<=100000。 ★数据输出

输出吃掉所有橙子所消耗的最低法力值（即移动距离之和的最小值）。

输入示例
5 2
1 2 1
2 3 2
3 4 2
4 5 1
输出示例
7

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+10;
int n,s,t;
vector<int> g[N];
bool vis[N];

void dfs(int u){
    if(vis[u])return ;
    vis[u]=true;
    for(auto v:g[u]){
        dfs(v);
    }
}

int main(){
    cin>>n>>s;
    t=n-s;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<n;++i)
        cin>>u>>v>>w;
    for(int i=1;i<n;++i)g[u].push_back(v),g[v].push_back(u);

    int ans=0;
    for(int i=s;i<t;++i){
        int cur=i;
        while(cur!=t && !vis[cur]){
            dfs(cur);
            ++cur;
        }
        ans+=cur-i;
    }

    cout<<ans;
    return 0;
}