链接:https://ac.nowcoder.com/acm/problem/13886
来源:牛客网
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld

题目描述

Today HH becomes a designer, and he faces a problem so he asks you for help.
Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.
HH the designer is going to design a plan to divide n city into n/2 pairs so that the sum of the length between the n/2 pairs city is minimum.
Now HH has finished it but he doesn't know whether it's true so he ask you to calculate it together.
It's guaranteed that n is even.

输入描述:

	
The first line contains an positive integer T(1≤T≤100), represents there are T test cases. 
For each test case: The first line contains an positive integer n(1≤n≤104), represents the number of cities in Treeisland, it's guarantee that n is even. 
Then n−1 lines followed. Each line contains three positive integer u, v and len, (u≠v,1≤u≤n,1≤v≤n,1≤len≤109)indicating there is a road of length len between u and v. 
It's guarantee you can get to any city from any city.

输出描述:

For each test case, output in one line an integer, represent the minimum sum of length.

第一次营业.....

题目大意:

有n个点,你需要将其每两个一组划分,将其划分为n/2个组,每组的权值定义为两个点之间的距离,求最小距离。

题目思路:


  1. 题目并不难,仔细分析一下即可得知为思维题:可惜我没有仔细分析
  2. 首先考虑特殊情况——叶子节点:叶子节点要选,由于树上的两点路径唯一,那么叶子节点的父边也一定要选。(记住这个一定!)
  3. 对于非叶子节点,考虑子树的个数,如果当前子树有偶数个,那么这偶数个之间绝对两两组合,但是如何两两组合?很简单的例子——菊花图,这时候两两组合就不是你想象中的两两组合。
  4. 菊花中心的点一旦被选必然会有一个点成为奇数点,那么要选这个奇数点,他的父边也一定要选。
  5. 所以由上可以看出:子树大小为奇数的父边一定要选!——联想就算偶数也是两个1组成
  6. 又因为需要贪心求解,所以我们只需要把必须选的边加到答案贡献里就可以了。
  7. 所以这题就变成了,判断一个子树的大小是否为奇数。
    talk is cheap ,show you the code .

    Code:

/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e16;
const int maxn=2e6+6;
const int mod=1000000007;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
struct dsu{int pre[maxn];void inint(){for(int i=1;i<=n;i++) pre[i]=i;}int Find(int x){return x==pre[x]?x:pre[x]=Find(pre[x]);}void Merge(int x,int y){int dx=Find(x),dy=Find(y);if(dx!=dy) pre[dx]=dy;}};
int pre[maxn];
int sz[maxn];
vector<pair<int,int>>v[maxn];
ll ans=0;
ll dfs(int u,int fa,int w){
    for(auto x:v[u]){
        if(x.first==fa) continue;
        dfs(x.first,u,x.second);
        sz[u]+=sz[x.first];
    }
    if(sz[u]&1) ans+=w;
    return sz[u];
}
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        read(n);
        ans=0;
        for(int i=1;i<=n;i++) v[i].clear(),sz[i]=1;
        for(int i=1;i<=n-1;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            v[x].push_back({y,z});
            v[y].push_back({x,z});
        }
        dfs(1,1,0);
        printf("%lld\n",ans);
    }
    return 0;
}
/***
2
1 2
0
2
query 1
query 2
***/