Submission

PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

Score: 100

User: detectives_conan

Problemset: Sirabyrinth 6

Language: cpp

Time: 0.029 second

Submitted On: 2025-03-14 16:22:16

/*
    Author : detective conan
    Problem : Sirabyrinth
    created : 14/03/2025 15:49 UTC+7
*/
#include <bits/stdc++.h>
#define FOR(i, s, t) for(int i = s; i <= t; ++i)
#define rep(i, s, t) for(int i = s; i >= t; --i)
#define HAVE_TESTCASE false
#define DB(n, s) cout << n << s
#define ANS(n, s) DB(n, s)
#define mod (int)(1e9 + 7)
#define sum(a, b) ((a%mod) + (b%mod))%mod
#define mul(a, b) ((a%mod) * (b%mod))%mod
#define conan cin.tie(nullptr)->sync_with_stdio(false)

using namespace std;
using i64 = int64_t;
using u64 = unsigned i64;
using u32 = unsigned;

const int MAX_N = 2e4 + 10;
int n, k, u, v, w[MAX_N], dp[MAX_N], ans, pre[MAX_N], mx, node;
vector<pair<int, int>> vc[MAX_N];
map<int, int> mp1;
map<pair<int, int>, int> edge;

void dfs(int u, int pa){
    for(auto x:vc[u]){
        int v = x.first, w = x.second;
        if(v == pa) continue;
        dp[v] = dp[u] + w;
        pre[v] = u;
        dfs(v, u);
    }
}

void solve(){
    cin >> n >> k, k++;
    FOR(i, 1, n - 1){
        cin >> u >> v >> w[i];
        u++, v++;
        mp1[w[i]]++;
        edge[{u, v}] = edge[{v, u}] = w[i];
        vc[u].emplace_back(v, w[i]);
        vc[v].emplace_back(u, w[i]);
    }
    dfs(k, -1);
    FOR(i, 1, n){
        if(mx < dp[i]){
            mx = dp[i];
            node = i;
        }
    }
    while(node != k){
        mp1[edge[{node, pre[node]}]]--;
        node = pre[node];
    }
    FOR(i, 1, n - 1){
        if(mp1[w[i]]) ans += w[i]*2, mp1[w[i]]--;
        else ans += w[i];
    }
    ANS(ans, '\n');
}

int main(){
    conan;
    int t = 1;
    if(HAVE_TESTCASE) cin >> t;
    while(t--) solve();
}