[Hackerearth] Leafonomics

Problem Link    : Leafonomics 
Category        : DP on Tree
Contest         : January Circuits '24 

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int INF = 1e18;
 
struct Node {
    int v, w;
    Node(int v = 0, int w = 0)
        : v(v), w(w) {}
};
 
int n;
vector<vector<Node>> graph;
vector<int> in;
 
void dfs(int u, int p) {
    int &mini = in[u];
    mini = INF;
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        dfs(v, u);
        mini = min(mini, w + in[v]);
    }
    if (mini == INF) {
        mini = 0;
    }
}
 
vector<int> out;
 
void solve(int u, int p) {
    int firstMin = INF;
    int secondMin = INF;
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        int cur = w + in[v];
        if (cur < firstMin) {
            secondMin = firstMin;
            firstMin = cur;
        } else if (cur < secondMin) {
            secondMin = cur;
        }
    }
    for (Node it : graph[u]) {
        int v = it.v;
        int w = it.w;
        if (v == p) {
            continue;
        }
        int use = w + in[v] == firstMin ? secondMin : firstMin;
        out[v] = min(w + out[u], w + use);
        solve(v, u);
    }
}
 
void solve() {
    cin >> n;
    graph.clear(); graph.resize(n + 1);
    for (int e = 1; e < n; e++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    in.clear(); in.resize(n + 1);
    dfs(1, 0);
    out.clear(); out.resize(n + 1, INF);
    solve(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << min(in[i], out[i]) << " \n"[i == n];
    }
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        solve();
    }
}