当前位置 博文首页 > 平凡人Kalzn的博客：小a与欧拉回路（树的直径的求法）
题目链接
这道题是一点思路都没有，看了别人的题解后，知道了答案其实是
ans = 树的总权值 * 2 - 树的直径；
首先，易知每个边最多复制两遍。思考后，可知，我们先假定每个边都复制了两遍，于是得到
树的总权值 * 2；
显然，我们算多了。于是我们考虑减去某些边，这里我们可以将树看作一个带有支路的一条主干道
这时我们从主干道的一端出发，到达另一端。那么此时主干道上的边可以只复制一次，而支路上的边要复制两次。所以，我们只要让这条“主干道”最长就好了，即为树的直径。于是就有上文的结论。
这里使用两次bfs求直径。
第一次：以任意点为起点，bfs出离当前点最远的一点point
第二次：以point为起点， bfs出离point最远的点的距离，该距离即为所求
下面是ac代码：
#include <iostream>
#include <cstring>
#include <queue>
#define ll long long
using namespace std;
const int MAX = 2000005;
int ver[2*MAX] = { 0 }, he[2*MAX] = { 0 }, ne[2*MAX] = { 0 };
int e[MAX] = { 0 };
bool vis[MAX] = { 0 };
ll dis[MAX] = { 0 };
int tot = 0;
int n;
void init()
{
tot = 0;
memset(e, 0, sizeof(e));
memset(ver, 0, sizeof(ver));
memset(he, 0, sizeof(he));
memset(ne, 0, sizeof(ne));
}
void add(int x, int y, int w)
{
ver[++tot] = y;
e[tot] = w;
ne[tot] = he[x];
he[x] = tot;
}
ll len = 0, point;
void bfs(int st)
{
queue<int> q;
while(q.size()) q.pop();
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
vis[st] = 1;
q.push(st);
while(q.size())
{
int te = q.front();
q.pop();
for (int i = he[te]; i; i = ne[i])
{
if (!vis[ver[i]])
{
vis[ver[i]] = 1;
dis[ver[i]] = dis[te] + e[i];
if (dis[ver[i]] > len)
{
len = dis[ver[i]];
point = ver[i];
}
q.push(ver[i]);
}
}
}
return;
}
int main()
{
cin >> n;
int x, y, w;
ll ans = 0;
for (int i = 1; i < n; i++)
{
scanf("%d%d%d", &x, &y, &w);
add(x, y, w);
add(y, x, w);
ans += w<<1;
}
len = 0;
bfs(1);
len = 0;
bfs(point);
printf("%lld\n", ans - len);
return 0;
}
