HDU 4118 Holiday's Accommodation

树形dp，好不容易中秋节做一场比赛，在hust上C上这道题怎么交怎么爆栈。。。无语了，上hdu一交就过了！！！

题目让求的是最远距离的和，两点间距离是最短路。画一下图，然后我们可以发现，因为是树形结构，所以对于边（u，v），只有边左边的点都通过这条边连边右边的点，才能使得总距离最远，于是就可以看出这是一道简单的树形dp了。这条边用的次数就是两边连的边数。。。

#pragma comment(linker, "/STACK:10240000000000,10240000000000")  
#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<fstream>  
#include<sstream>  
#include<vector>  
#include<string>  
#include<cstdio>  
#include<bitset>  
#include<queue>  
#include<stack>  
#include<cmath>  
#include<map>  
#include<set>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))

using namespace std;

const int N=111111;

struct Edge
{
    int u, v;
    LL len;
}E[N << 1];

int fir[N], next[N << 1], tot;

void Add_Edge(int u, int v, LL len)
{
    E[tot].u = u, E[tot].v = v;E[tot].len = len;
    next[tot] = fir[u], fir[u] = tot ++;
}

LL ans;
int n;

int dfs(int u, int fa)
{
    int v, i, ret = 1, hav;
    for(i = fir[u]; ~i; i = next[i])
    {
        v = E[i].v;
        if(v != fa)
        {
            hav = dfs(v, u);
            ret += hav;
            ans += 2 * E[i].len * min(hav, n - hav);
        }
    }
    return ret;
}

int main()
{
    int i, j, u, v, cas = 1, t;
    LL len;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &n);
        CLR(fir, -1);tot = 0;
        for(i = 1; i < n; i ++)
        {
            scanf("%d%d%I64d", &u, &v, &len);
            Add_Edge(u, v, len);
            Add_Edge(v, u, len);
        }
        ans = 0;
        dfs(1, -1);
        printf("Case #%d: %I64d\n", cas ++, ans);
    }
}