Submission

PPPPPPPPPPPPPPPPPPPPPPPPPPPPPP

Score: 100

User: Dormon

Problemset: Sirabyrinth 6

Language: cpp

Time: 0.016 second

Submitted On: 2025-03-14 16:34:19

#include <iostream>
#include <vector>

using namespace std;
const int N = 2e4+2;

vector<pair<int, int>> adj[N];
int dp1[N], dp2[N];

int dfs1(int u, int pre){
    for (auto [v, w]:adj[u]){
        if (v == pre) continue;
        dp1[u] += w + dfs1(v, u);
    }
    return dp1[u];
}

int dfs2(int u, int pre){
    for (auto [v, w]:adj[u]){
        if (v == pre) continue;
        dp2[u] = max(dp2[u], w + dfs2(v, u));
    }
    return dp2[u];
}

int main()
{
    int n, st;
    cin >> n >> st;

    for (int i = 1;i < n;i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    cout << 2 * dfs1(st, -1) - dfs2(st, -1) << '\n';
}