【CF1280】C. Jeremy Bearimy（贪心）

题目链接：https://codeforc.es/contest/1280/problem/C

分析

**最小值：**根据贪心策略，我们每一条边用的次数要尽量少，如果一条边的两边都有偶数个点，那么这条边肯定不用；相反的，如果一条边两边都有奇数个点，那么这条边不得不用，因为奇数个点不足以都凑成对，必须跨边去借点。

**最大值：**类似于最小值的思路，每一条边我们要用尽量多的次数，如果一条边的两边分别有$n$，$2k?n$个点，那么这条边最多可以被用到$min(n,2k?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;
}