抄完题解之好像不难系列
求最小，用dfs，尽可能选择相邻的点对，如果以某个儿子为顶点的子树sz为odd，则儿子v与当前节点u所连的边必取，儿子v的其余点两两相连1，与u无关。
因此，只需要统计子树大小为奇数的v与其父亲u之间这条边的权值。
求最大，同样基于dfs。画一张图我们可以看出来，越靠近“中间”的边被统计的次数更多。然后我们发现，最”中间“的点实质上是树的重心。
对于某一条边u——v，以这条边为界将整棵树一分为二，sz[u]和sz[v]的较小值即是这条边在统计中至多被取到的次数。
假设有一对点位于u——v的同侧，那么通过交换，我们发现，位于两侧势必能获得更大的权值和。
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std;
4 const int N = 1e5 + 10;
5
6 ll ans1, ans2, k;
7 ll head[N << 1], sz[N << 1], tot;
8
9 struct edge
10 {
11 int to, next;
12 ll w;
13 }e[N << 2];
14
15 inline void add_edge(int u, int v, ll w)
16 {
17 e[tot].next = head[u];
18 e[tot].to = v;
19 e[tot].w = w;
20 head[u] = tot++;
21 }
22
23 void dfs(int u, int f)
24 {
25 sz[u] = 1;
26 for(int i = head[u] ; ~i ; i = e[i].next){
27 int v = e[i].to;
28 if(v == f) continue;
29 ll w = e[i].w;
30 dfs(v, u);
31 sz[u] += sz[v];
32 if(sz[v] % 2 == 1) ans1 += w;
33 //如果以某个儿子为顶点的子树sz为odd，则儿子v与当前节点u所连的边必取
34 ans2 += 1ll * w * min(sz[v], 2ll * k - sz[v]);//
35 }
36 }
37
38 int main(){
39 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
40 int t; cin >> t;
41 while(t--)
42 {
43 cin >> k;
44 for(int i = 0 ; i < (N << 1) ; i++){
45 head[i] = -1, sz[i] = 0;
46 }tot = ans1 = ans2 = 0;
47 for(int i = 1 ; i <= (k * 2 - 1) ; i++){
48 int u, v; ll val;
49 cin >> u >> v >> val;
50 add_edge(u, v, val);
51 add_edge(v, u, val);
52 }
53 dfs(1, -1);
54 cout << ans1 << " " << ans2 << endl;
55 }
56
57 return 0;
58 }
学习途径：https://www.cnblogs.com/Anonytt/p/13623738.html