题解

题解传送门

code

#include <bits/stdc++.h>
using namespace std; 
const int maxn = 2e5 + 100;
const int maxm = 4e5 + 100; 

template <typename T>
inline void read(T &s) {
    s = 0; 
    T w = 1, ch = getchar(); 
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w; 
} 

template <typename T> 
inline void write(T s) {
    T w = 0, c[15]; 
    if (s < 0) putchar('-'), s = -s; 
    while(s) c[++w] = (s % 10) + 48, s /= 10;
    while(w) putchar(c[w--]); 
}

template <typename T>
inline void output(T size, T arr[maxn]) {
    for (int i = 1; i <= size; ++i) {
        printf("%d ", arr[i]); 
    }
    puts(""); 
}

inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a < b ? a : b; }

int T, n, tot, cnt, ans; 
int lin[maxn], deg[maxn], snk[maxn], d[maxn], f[maxn]; 
bool vis[maxn]; 
struct node {
    int next, to, dis; 
} edge[maxm]; 

inline void add(int from, int to, int dis) {
    deg[to]++; 
    edge[++tot].to = to;
    edge[tot].dis = dis; 
    edge[tot].next = lin[from]; 
    lin[from] = tot; 
}

void dp(int x) {
    vis[x] = true; 
    d[x] = 0; 
    for (int i = lin[x]; i; i = edge[i].next) {
        int y = edge[i].to; 
        if (vis[y]) continue; 
        dp(y); 
        if (deg[y] == 1) d[x] += edge[i].dis; 
        else d[x] += min(d[y], edge[i].dis); 
    }
}

void dfs(int x) {
    vis[x] = true; 
    for (int i = lin[x]; i; i = edge[i].next) {
        int y = edge[i].to;
        if (vis[y]) continue; 
        if (deg[x] == 1) f[y] = d[y] + edge[i].dis; 
        else f[y] = d[y] + min(f[x] - min(d[y], edge[i].dis), edge[i].dis); 
        dfs(y); 
    }
}

int main() {
    read(T); 
    while (T--) {
        tot = 0;
        cnt = 0; 
        ans = -1;   
        memset(deg, 0, sizeof(deg)); 
        memset(lin, 0, sizeof(lin)); 

        read(n);
        for (int i = 1; i < n; ++i) {
            int x, y, z; 
            read(x), read(y), read(z); 
            add(x, y, z); 
            add(y, x, z); 
        }

        int root = 1; 
        memset(d, 0x3f, sizeof(d)); 
        memset(vis, false, sizeof(vis));
        dp(root);

        memset(vis, false, sizeof(vis)); 
        f[root] = d[root]; 
        dfs(root);  

        for (int i = 1; i <= n; ++i) {
            ans = max(ans, f[i]); 
        }

        write(ans), putchar('\n');  
    }
    return 0; 
}