3264번: ONE

https://www.acmicpc.net/problem/3264


$O(n)$

답은 (모든 간선 가중치 합)*2-(s에서 가장 먼 교차점까지의 거리)

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, s, tot;
vector<pair<int, int> > adj[100001];
int f(int h, int p) {
    int m = 0;
    for (auto it : adj[h]) if (it.first^p) m = max(m, it.second + f(it.first, h));
    return m;
}
int main() {
    scanf("%d%d", &n, &s);
    for (int i = 1, a, b, c; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
        tot += c;
    }
    printf("%d", tot * 2 - f(s, 0));
    return 0;
}