PROG-T1111: Capital

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

typedef long long lli;
typedef pair<int, int> pii;

const int N = 1e5 + 1;

vector<pii> adj[N + 1];
vector<lli> dp(N + 1, -1);
int nVertex;

lli DFS(int u, int p){
    if(dp[u] != -1){
        return dp[u];
    }
    lli mx = 0;
    for(pii nxt : adj[u]){
        int v = nxt.first;
        int w = nxt.second;
        if(v != p){
            mx = max(mx, w + DFS(v, u));
        }
    }
    return dp[u] = mx;
}

int main(){

    scanf("%d", &nVertex);

    for(int i = 1; i < nVertex; ++i){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    cout << DFS(1, 0);

    return 0;
}