Graph theory (tree diameter)

One 、 Basics

The distance between the two farthest nodes in a tree is called the diameter of the tree , The path connecting these two points is called the longest chain of the tree （ Also called diameter ）

Two 、 Twice traversal to find the diameter

1、 Starting from any node , adopt bfs perhaps dfs Traverse the tree once , Find the node farthest from the starting point , Write it down as p, This is the diameter end of the tree

2、 From the node p set out , adopt bfs and dfs Traverse the tree again , Work out with p The farthest node , Write it down as q

3、 that p To q The path of is a diameter of the tree , because p It must be the end of the diameter , Otherwise, a longer chain will always be found . In the second step of traversal , You can record the precursor node of each point when it is accessed for the first time , Finally from the q Go back to p The specific scheme of diameter can be obtained

4、 notes ： The problem of negative edge weight cannot be solved by searching

int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int cnt, n, m, r;
ll  dis[maxn], maxd, maxv;
void add(int u, int v, int w)
{
	to[++cnt] = v;
	edge[cnt] = w;
	nex[cnt] = head[u];
	head[u] = cnt;
}
void dfs(int u, int fa)
{
	if (maxd < dis[u])
	{
		maxd = dis[u];
		maxv = u;
	}
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (fa == v)
			continue;
		dis[v] = dis[u] + edge[i];
		dfs(v, u);
	}
}
void solve()
{
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dfs(1, 0);
	maxd = 0;
	dis[maxv] = 0;
	dfs(maxv, 0);
	cout << maxd;
}

3、 ... and 、 Tree form dp Find the diameter

1、 set up d[x] Represents a slave node x Set out to x Root subtree , The distance of the farthest node that can be reached , namely x The longest chain that goes down , Obviously there is

2、 So we can think about finding each point through x The length of the longest chain f[x], Then the diameter of the whole tree is the largest f[x]. about x Any two nodes of yi,yj, Through the nodes x The length of the longest chain consists of four parts , as follows

3、 When child nodes are enumerated to i when ,d[x] Just saved from x Departure direction yi Is the distance of the farthest node that can be reached by the subtree of the root , This distance is , So let's use to update f[x], Reuse to update d[x] that will do

int to[maxn << 1], nex[maxn << 1], edge[maxn << 1], head[maxn];
int vis[maxn];
int cnt, n, m, r;
ll ans = 0, d[maxn];
void add(int u, int v, int w)
{
	to[++cnt] = v;
	edge[cnt] = w;
	nex[cnt] = head[u];
	head[u] = cnt;
}
void dp(int u)
{
	vis[u] = 1;
	for (int i = head[u]; i; i = nex[i])
	{
		int v = to[i];
		if (vis[v])
			continue;
		dp(v);
		ans = max(ans, d[u] + d[v] + edge[i]);
		d[u] = max(d[u], d[v] + edge[i]);
	}
}
void solve()
{
	cin >> n;
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	dp(1);
	cout << ans << '\n';
}