题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3534
题意：
给你一棵树，问你有多少对点的距离等于树的直径。
思路：
dp[i][0]表示在i的子树中 离i最远的距离，dp[i][1]是次远距离。 cnt[i][0]则是最远的点的数量，cnt[i][1]表示次远的数量。
up[i]表示以i向上 离i最远的距离。 up_cnt[i]表示向上最远的数量。
写的有点麻烦，调试了2小时。。。
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 2e5 + ;
int dp[N][];
int cnt[N][];
int up[N];
int cnt_up[N];
int son[N][];
vector <P> G[N]; void dfs1(int u, int p) {
dp[u][] = dp[u][] = ;
son[u][] = son[u][] = u;
cnt[u][] = cnt[u][] = ;
int tmp = ;
for(int i = ; i < G[u].size(); ++i) {
P temp = G[u][i];
int v = temp.first;
if(v == p)
continue;
dfs1(v, u);
if(dp[v][] + temp.second > dp[u][]) {
dp[u][] = dp[u][];
son[u][] = son[u][];
cnt[u][] = cnt[u][];
dp[u][] = dp[v][] + temp.second;
son[u][] = v;
cnt[u][] = cnt[v][];
tmp = cnt[v][];
} else if(dp[v][] + temp.second == dp[u][]) {
cnt[u][] += cnt[v][];
cnt[u][] = cnt[u][] - tmp;
dp[u][] = dp[u][];
son[u][] = v;
} else if(dp[v][] + temp.second > dp[u][]) {
dp[u][] = dp[v][] + temp.second;
cnt[u][] = cnt[v][];
son[u][] = v;
} else if(dp[v][] + temp.second == dp[u][]) {
cnt[u][] += cnt[v][];
}
}
} void dfs2(int u, int p) {
for(int i = ; i < G[u].size(); ++i) {
P temp = G[u][i];
int v = temp.first;
if(v == p)
continue;
if(dp[u][] == temp.second + dp[v][]) {
//up[v] = max(up[u], dp[u][0]) + temp.second;
if(dp[u][] == ) {
cnt_up[v] = cnt_up[u];
up[v] = up[u] + temp.second;
dfs2(v, u);
continue;
}
if(up[u] > dp[u][]) {
up[v] = up[u] + temp.second;
cnt_up[v] = cnt_up[u];
} else if(dp[u][] > up[u]) {
up[v] = dp[u][] + temp.second;
if(dp[u][] == dp[u][])
cnt_up[v] = cnt[u][] - cnt[v][];
else
cnt_up[v] = cnt[u][];
} else {
if(dp[u][] == dp[u][])
cnt_up[v] = cnt[u][] - cnt[v][];
else
cnt_up[v] = cnt[u][];
cnt_up[v] += cnt_up[u];
up[v] = dp[u][] + temp.second;
}
} else {
//up[v] = max(up[u], dp[u][1]) + temp.second;
if(up[u] > dp[u][]) {
up[v] = up[u] + temp.second;
cnt_up[v] = cnt_up[u];
} else if(dp[u][] > up[u]) {
up[v] = dp[u][] + temp.second;
cnt_up[v] = cnt[u][];
} else {
cnt_up[v] = cnt_up[u] + cnt[u][];
up[v] = dp[u][] + temp.second;
}
}
dfs2(v, u);
}
} int main()
{
int n, u, v, c;
while(~scanf("%d", &n)) {
for(int i = ; i <= n; ++i) {
G[i].clear();
}
for(int i = ; i < n; ++i) {
scanf("%d %d %d", &u, &v, &c);
G[u].push_back(make_pair(v, c));
G[v].push_back(make_pair(u, c));
}
dfs1(, -);
cnt_up[] = ;
dfs2(, -);
int Max = ;
for(int i = ; i <= n; ++i) {
//cout << dp[i][0] << " - " << up[i] << endl;
Max = max(Max, max(dp[i][], up[i]));
}
LL ans = ;
for(int i = ; i <= n; ++i) {
if(Max == dp[i][]) {
ans += (LL)cnt[i][];
}
if(Max == up[i]) {
ans += (LL)cnt_up[i];
}
}
printf("%d %lld\n", Max, ans/);
}
return ;
}