题解 | #小A与欧拉路#

1. 树的直径
   
2. 题解
   

树的直径

树的直径的定义:图中两个叶子节点的最长距离
定义$d1[i]d1[i]$表示以$ii$为根节点到叶子节点的最长距离
定义$d2[i]d2[i]$表示以$ii$为根节点到叶子节点的次最长距离
定义$mp[i][j]mp[i][j]$表示从$ii$到$jj$的距离 若$verver$为$fafa$的子节点，动态转换方程可以写成：


最后最大距离为$d=max(d1[i],d2[i])d=max(d1[i],d2[i])$

void dfs(int u, int fa)
{
	d1[u] = d2[u] = 0;
	for (node v : E[u])
	{
		if (v.to == fa)
			continue;
		dfs(v.to, u);
		long long  t = d1[v.to] + v.w;
		if (t > d1[u])
			d2[u] = d1[u], d1[u] = t;
		else if (t > d2[u])
			d2[u] = t;
	}
	d = max(d, d1[u] + d2[u]);
}

题解

欧拉回路是起点和终点是同一个点，题中的每个边都走两遍就可以形成欧拉回路。本题的图是求一个最小的欧拉路径，所以我们将刚才的欧拉回路减去一个树的直径即可。
AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 200;

struct node
{
	long long to, w;
};
long long n, d = 0, d1[N], d2[N];
vector<node> E[N];

void dfs(int u, int fa)
{
	d1[u] = d2[u] = 0;
	for (node v : E[u])
	{
		if (v.to == fa)
			continue;
		dfs(v.to, u);
		long long t = d1[v.to] + v.w;
		if (t > d1[u])
			d2[u] = d1[u], d1[u] = t;
		else if (t > d2[u])
			d2[u] = t;
	}
	d = max(d, d1[u] + d2[u]);
}

int main()
{
	scanf("%d", &n);
	long long sum = 0;
	for (int i = 1; i < n; i++)
	{
		long long u, v, w;
		scanf("%lld %lld %lld", &u, &v, &w);
		sum += 2 * w;
		E[u].push_back({v, w}), E[v].push_back({u, w});
	}
	dfs(1, 0);
	printf("%lld\n", sum - d);
	return 0;
}