1207.大臣的旅费
题上说从首都到城市的方案唯一,,,说明没有环,那路径就是一棵以首都为根节点,的数.
这个题就是树形图中的最长路径
先找到离root最远的点,再找到离这个点最远的点
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 2 * N;
long long h[N], e[M], ne[M], w[M], idx;
int n;
long long ans;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
long long dfs(int u, int father)
{
long long dist = 0;
long long d1 = 0, d2 = 0;
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if(v == father) continue;
long long d = dfs(v, u) + w[i];
dist = max(dist, d);
if(d >= d1) d2 = d1, d1 = d;
else if(d > d2) d2 = d;
}
ans = max(ans, d1 + d2);
return dist;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
dfs(1, -1);
cout << 10*ans+(1 + ans)*ans/2 << endl;
return 0;
}