树上最长路的O(n)算法

本文主要是介绍树上最长路的O(n)算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

关于如何求得树中每个点最长路的O(n)算法：

1.算法流程：

• 求出树上的直径，在第二次dfs中求出从直径一端点到每个点的距离
  再跑一次dfs，求出另一端点到每个点的距离，并更新每个点的最长路

2. 算法实现：

#include<bits/stdc++.h>
#define ll long long
#define N 10000005
#define f1(i,n,m) for(int i=n;i<=m;++i)
using namespace std;
template<typename T>
void read(T &x) {
	int w = 1;
	x = 0;
	char c = getchar();
	while (c < '0' || c > '9') {if (c == '-')w = -1;c = getchar();}
	while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + c - '0';c = getchar();}
	x *= w;
}
int tot, n, m, cnt, ans, root, mx;
int l1 = 0, l2 = 0, r1 = 1, r2 = 1, top = 1;
int head[N], to[N], nex[N], w[N];
int len[N], q1[N], q2[N], num[N];
void add(int x, int y, int wi) {
	to[++tot] = y;
	w[tot] = wi;
	nex[tot] = head[x];
	head[x] = tot;
}
void dfs(int x, int f, int dep) {
	int y;
	if (len[x] < dep)len[x] = dep;
	if (dep >= mx)mx = dep, root = x;
	for (int i = head[x]; i; i = nex[i]) {
		y = to[i];
		if (y == f)continue;
		dfs(y, x, dep + w[i]);
	}
}
void move(int top) {
	if (top > n)return;
	while (len[q1[r1]] < len[top] && l1 <= r1)r1--;
	while (len[q2[r2]] > len[top] && l2 <= r2)r2--;
	q1[++r1] = top, q2[++r2] = top;
}
signed main() {
	int x, y;
	read(n), read(m);
	f1(i, 2, n) {
		read(x), read(y);
		add(i, x, y);
		add(x, i, y);
	}
	dfs(1, 0, 0);
	dfs(root, 0, 0);
	dfs(root, 0, 0);
	f1(i, 1, n) {
		while (top <= n + 1 && len[q1[l1]] - len[q2[l2]] <= m)
			ans = max(ans, top - i), move(top++);
		if (l1 <= r1 && q1[l1] <= i)l1++;
		if (l2 <= r2 && q2[l2] <= i)l2++;
	}
	printf("%d", ans);
}

3. 算法依据：

树上任意一点的最长路的一端必定在这棵树某个直径的一个端点

4. 算法证明：

这篇关于树上最长路的O(n)算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！