题目链接：https://codeforc.es/contest/1280/problem/C
Welcome! Everything is fine.
You have arrived in The Medium Place, the place between The Good Place and The Bad Place. You are assigned a task that will either make people happier or torture them for eternity.
You have a list of k pairs of people who have arrived in a new inhabited neighborhood. You need to assign each of the 2k people into one of the 2k houses. Each person will be the resident of exactly one house, and each house will have exactly one resident.
Of course, in the neighborhood, it is possible to visit friends. There are 2k?1 roads, each of which connects two houses. It takes some time to traverse a road. We will specify the amount of time it takes in the input. The neighborhood is designed in such a way that from anyone’s house, there is exactly one sequence of distinct roads you can take to any other house. In other words, the graph with the houses as vertices and the roads as edges is a tree.
The truth is, these k pairs of people are actually soulmates. We index them from 1 to k. We denote by f(i) the amount of time it takes for the i-th pair of soulmates to go to each other’s houses.
As we have said before, you will need to assign each of the 2k people into one of the 2k houses. You have two missions, one from the entities in The Good Place and one from the entities of The Bad Place. Here they are:
The first mission, from The Good Place, is to assign the people into the houses such that the sum of f(i) over all pairs i is minimized. Let’s define this minimized sum as G. This makes sure that soulmates can easily and efficiently visit each other;
The second mission, from The Bad Place, is to assign the people into the houses such that the sum of f(i) over all pairs i is maximized. Let’s define this maximized sum as B. This makes sure that soulmates will have a difficult time to visit each other.
What are the values of G and B?
Input
The first line of input contains a single integer t (1≤t≤500) denoting the number of test cases. The next lines contain descriptions of the test cases.
The first line of each test case contains a single integer k denoting the number of pairs of people (1≤k≤105). The next 2k?1 lines describe the roads; the i-th of them contains three space-separated integers ai,bi,ti which means that the i-th road connects the ai-th and bi-th houses with a road that takes ti units of time to traverse (1≤ai,bi≤2k, ai≠bi, 1≤ti≤106). It is guaranteed that the given roads define a tree structure.
It is guaranteed that the sum of the k in a single file is at most 3?105.
Output
For each test case, output a single line containing two space-separated integers G and B.
Example
input
2
3
1 2 3
3 2 4
2 4 3
4 5 6
5 6 5
2
1 2 1
1 3 2
1 4 3
output
15 33
6 6
题意
给定 2 * k 个点,问选择k对点（每个点都必须选上）进行相连，求出所有路径之和。求出路径之和的最小值和最大值。
分析
最小值：根据贪心策略，我们每一条边用的次数要尽量少，如果一条边的两边都有偶数个点，那么这条边肯定不用；相反的，如果一条边两边都有奇数个点，那么这条边不得不用，因为奇数个点不足以都凑成对，必须跨边去借点。
最大值：类似于最小值的思路，每一条边我们要用尽量多的次数，如果一条边的两边分别有 n ，2 * k - n 个点，那么这条边最多可以被用到 min(n, 2 * k - n) 次，这样我们就可以找到最大值。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N = 300007;
int t,k,n;
struct node{
int v,w;
};
vector<node> g[N];
int vis[N], sum[N];
ll maxn,minn;void dfs(int x)
{
vis[x] = 1;sum[x] = 1;for(int i=0;i<g[x].size();i++){
int v = g[x][i].v, w = g[x][i].w;if(vis[v] == 1) continue;dfs(v);sum[x] += sum[v];if(sum[v] & 1) minn += w;maxn += 1ll * w * min(sum[v], n - sum[v]);}
}int main()
{
scanf("%d",&t);while(t--){
scanf("%d",&k);n = 2 * k;for(int i=1;i<=n;i++) g[i].clear(), vis[i] = 0;for(int i=1;i<=n-1;i++){
int u,v,w;scanf("%d%d%d",&u,&v,&w);g[u].push_back({
v, w});g[v].push_back({
u, w});}vis[1] = 1;minn = maxn = 0;dfs(1);printf("%lld %lld\n",minn, maxn);}return 0;
}