牛客练习赛27 C. 水图(dfs+思维)

#include <bits/stdc++.h>
#define maxn 50005
#define ll long long
using namespace std;
struct Node{
    int to;
    ll w;
    int next;
}Edge[maxn << 1];
int head[maxn << 1];
int n,s,num;
ll maxx;

void init(){
    memset(head,-1,sizeof(head));
    num = 0;
}

void add(int u,int v,ll w){
    Edge[num].to = v;
    Edge[num].w = w;
    Edge[num].next = head[u];
    head[u] = num++;
}

void dfs(int x,int xx,ll step){
    maxx = max(maxx, step);
    for(int i=head[x];i!=-1;i=Edge[i].next){
        if(Edge[i].to == xx)continue;
        dfs(Edge[i].to, x, step + Edge[i].w);
    }
}

int main()
{
    init();
    scanf("%d%d",&n,&s);
    ll sum = 0;
    for(int i=1;i<n;i++){
        int u,v;
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
        sum += w;
    }
    maxx = 0;
    dfs(s, 0, 0);
    cout<<sum * 2 - maxx<<endl;
    return 0;
}