题目链接：https://vjudge.net/problem/UVALive-6039
本场总题解：http://blog.csdn.net/bright_xl/article/details/10827747
http://blog.csdn.net/sdj222555/article/details/10908015
http://blog.csdn.net/ok_again/article/details/14012217

//对于这个题，由于不确定最优化方法从哪里寻找他的起点，所以我们把每个节点都计算一遍
//这样找到的节点数就是总的路径条数的两倍（因为起点和终点重合，终点又当了一次起点）
//这是路径方面
//其次，在计算每个节点时，我们采用某种规则进行计算，
//首先对于非叶子节点，即向周围连接分叉大于一个的节点
//我们先计算两个值，mmax，sum一个是所有路径的和，一个是拥有最大权值的那个分叉的权值（即其所带的路径条数）
//例如（6 1 1 1 1 1）mmax = 6，sum = 11
//当（1）mmax>sum-mmax(即除了最大权值分叉的其他分叉所带的路径总和) 时，这时候由偶数配对原则可得所得起点数mmax-(sum-mmax)，例如（6 1 1 1 1 1），对于当前节点来说起点数就是6-5;
//而当（2）mmax<sum-mmax时，这时候算得的起点最多只有一个（当总和为偶数时，所有路径都可以两两配对，此处不存在起点）即当总和为奇数时
//对于叶子节点
//此规则同样适用
//
//注意(1)也可以表示为 mmax>sum/2 (可以证明,令b = sum - mmax,假如mmax>sum/2,mmax*2>sum,mmax+mmax>b+mmax,即mmax>b,即mmax>b等价于mmax*2>sum )
//同理(2)也可以表示为 mmax<sum/2

code：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;

struct node
{
    int sum[100001],mmax[100001];//sum存储的是每个节点周围连接路径的总和，
    //mmax存储的则是周围所有连接路径的拥有最大条数的那一个分叉
}o;//结构体内建立数组，便于初始化

int main()
{
    int T,a,b,c,cas =0 ;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        cin>>n;
        memset(o.mmax,0,sizeof(o.mmax));
        memset(o.sum,0,sizeof(o.sum));
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            o.mmax[a] = max(o.mmax[a],c);
            o.mmax[b] = max(o.mmax[b],c);
            o.sum[a]+=c;
            o.sum[b]+=c;
        }
        int s = 0;
        for(int i=1;i<=n;i++)
        {
            if(o.mmax[i]*2>o.sum[i])//mmax>sum-mmax时
            {
                s +=o.mmax[i]*2-o.sum[i];
            }
            else if(o.sum[i]%2==1)
            {
                s+=1;
            }
        }
        printf("Case #%d: %d\n", ++cas, s/2);
    }
    return 0;
}