http://acm.hdu.edu.cn/showproblem.php?pid=3534

main.cpp

#include <cstdio>
#include <vector>

using namespace std;

int n;
vector<vector<pair<int, int> > > g;
vector<bool> vis;
int ans;
int cnt;

pair<int, int> dfs(int s) {
	vector<pair<int, int> > rets;
	for (int i = 0; i < g[s].size(); i++) {
		int r = g[s][i].first, v = g[s][i].second;
		if (!vis[r]) {
			vis[r] = true;
			pair<int, int> ret = dfs(r);
			rets.push_back(make_pair(ret.first + v, ret.second));
		}
	}
	if (rets.size() == 0) {
		return make_pair(0, 1);
	} else if (rets.size() == 1) {
		if (ans < rets[0].first) {
			ans = rets[0].first;
			cnt = rets[0].second;
		} else if (ans == rets[0].first) {
			cnt += rets[0].second;
		}
		return rets[0];
	}
	int mx = 0;
	int cntmx = 0;
	int the2 = 0;
	for (unsigned int i = 0; i < rets.size(); i++) {
		if (mx < rets[i].first) {
			mx = rets[i].first;
			cntmx = 1;
			the2 = rets[i].second;
		} else if (mx == rets[i].first) {
			cntmx++;
		}
	}
	if (cntmx == 1) {
		int mxx = 0;
		for (unsigned int i = 0; i < rets.size(); i++) {
			if (rets[i].first < mx && mxx < rets[i].first) {
				mxx = rets[i].first;
			}
		}
		int sum = 0;
		for (unsigned int i = 0; i < rets.size(); i++) {
			if (rets[i].first == mxx) {
				sum += rets[i].second;
			}
		}
		int c = sum * the2;
		if (ans < mx + mxx) {
			ans = mx + mxx;
			cnt = c;
		} else if (ans == mx + mxx) {
			cnt += c;
		}
		return make_pair(mx, the2);
	}
	int c = 0;
	int sum = 0;
	for (unsigned int i = 0; i < rets.size(); i++) {
		if (rets[i].first == mx) {
			c += sum * rets[i].second;
			sum += rets[i].second;
		}
	}
	if (ans < mx + mx) {
		ans = mx + mx;
		cnt = c;
	} else if (ans == mx + mx) {
		cnt += c;
	}
	return make_pair(mx, sum);
}

int main() {
	while (scanf("%d", &n) == 1) {
		g.clear();
		g.resize(n + 1);
		vis.clear();
		vis.resize(n + 1);
		for (int i = 0; i < n - 1; i++) {
			int l, r, v;
			scanf("%d%d%d", &l, &r, &v);
			g[l].push_back(make_pair(r, v));
			g[r].push_back(make_pair(l, v));
		}
		ans = 0;
		cnt = 0;
		vis[1] = true;
		dfs(1);
		printf("%d %d\n", ans, cnt);
	}
	return 0;
}