蓝桥杯2013年第四届真题-大臣的旅费 （C++代码）

        树的直径    

参考代码:

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;

const int SIZE = 5E4;
vector<pair<int, int> > vec[SIZE];
bool Vis[SIZE];

pair<int, int> DFS(int now) {
	Vis[now] = 1;
	pair<int, int> nowpos = make_pair(now, 0);
	for (int pos = 0; pos < vec[now].size(); pos++) {
		pair<int, int> next = vec[now][pos];
		if (Vis[next.first])
			continue;
		pair<int, int> tmp = DFS(next.first);
		if (next.second + tmp.second > nowpos.second) {
			nowpos = tmp;
			nowpos.second += next.second;
		}
	}
	return nowpos;
}

int spend(int dis) {
	return (11 + 10 + dis) * dis / 2;
}

int main() {
	int form, to, w, total;
	scanf("%d", &total);
	for (int pos = 1; pos < total; pos++) {
		scanf("%d%d%d", &form, &to, &w);
		vec[form].push_back(make_pair(to, w));
		vec[to].push_back(make_pair(form, w));
	}
	pair<int, int> tmp = DFS(1);
	memset(Vis, false, sizeof(Vis));
	printf("%d\n", spend(DFS(tmp.first).second));
}