标签：int top dfs 算法 树上 最长 define
关于如何求得树中每个点最长路的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. 算法证明：
标签：int,
top,
dfs,
算法,
树上,
最长,
define
From： https://www.cnblogs.com/windf/p/16659748.html