1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e5 + 5;17 struct Edge {18     int next, to, cost;19 }edge[N << 1];20 int head[N], tot;21 P d[N], pos[N];22 int up[N];23 24 void init(int n) {25     memset(head, -1, sizeof(head));26     tot = 0;27     for(int i = 0; i <= n; ++i) {28         d[i].first = d[i].second = 0;29         pos[i].first = pos[i].second = -1;30         up[i] = 0;31     }32 }33 34 inline void add(int u, int v, int cost) {35     edge[tot].next = head[u];36     edge[tot].to = v;37     edge[tot].cost = cost;38     head[u] = tot++;39 }40 41 void dfs1(int u, int p) {42     for(int i = head[u]; ~i; i = edge[i].next) {43         int v = edge[i].to;44         if(v == p)45             continue;46         dfs1(v, u);47         if(d[v].first + edge[i].cost > d[u].first) {48             if(d[u].first != 0)49                 d[u].second = d[u].first;50             d[u].first = d[v].first + edge[i].cost;51             pos[u].first = v;52         } else if(d[v].first + edge[i].cost > d[u].second) {53             d[u].second = d[v].first + edge[i].cost;54             pos[u].second = v;55         }56     }57 }58 59 void dfs2(int u, int p) {60     for(int i = head[u]; ~i; i = edge[i].next) {61         int v = edge[i].to;62         if(v == p) 63             continue;64         if(v == pos[u].first) {65             up[v] = max(up[u], d[u].second) + edge[i].cost;66         } else {67             up[v] = max(up[u], d[u].first) + edge[i].cost;68         }69         dfs2(v, u);70     }71 }72 73 int main()74 {75     int t, n;76     scanf("%d", &t);77     for(int ca = 1; ca <= t; ++ca) {78         scanf("%d", &n);79         init(n);80         int u, v, cost;81         for(int i = 1; i < n; ++i) {82             scanf("%d %d %d", &u, &v, &cost);83             add(u, v, cost);84             add(v, u, cost);85         }86         dfs1(0, -1);87         dfs2(0, -1);88         printf("Case %d:\n", ca);89         for(int i = 0; i < n; ++i) {90             printf("%d\n", max(d[i].first, up[i]));91         }92     }93     return 0;94 }