Description：

给定一棵有 $n$ 个节点的树，求每个节点到其他节点的最大距离。

$1\leqslant n\leqslant 10^4$

Solution1：

有一个性质就是先随便找出来一个直径，那么和一个点距离最远的点一定可以是直径的一个端点，因为如果是别的点可以换到直径上更长，所以树剖就行了。

Code1：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 10010

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

struct edge

{

	int to,nxt,w;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].w = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].w = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int fa[MAXN],siz[MAXN],son[MAXN],top[MAXN],dep[MAXN];

void dfs1(int k,int depth)

{

	siz[k] = 1;dep[k] = depth;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		dfs1(e[i].to,depth + 1);

		siz[k] += siz[e[i].to];

		if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

		{

			son[k] = e[i].to;

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int dis[MAXN];

int BFS(int s)

{

	queue<int> q;q.push(s);

	memset(dis,0x3f,sizeof(dis));

	dis[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(dis[e[i].to] > dis[k] + e[i].w)

			{

				dis[e[i].to] = dis[k] + e[i].w;

				q.push(e[i].to);

			}

		}

	}

	int d = 0,ans;

	for(int i = 1;i <= n;++i)

	{

		if(dis[i] > d)

		{

			d = dis[i];

			ans = i;

		}

	}

	return ans;

}

int dist(int a,int b){return dis[a] + dis[b] - 2 * dis[LCA(a,b)];}

int main()

{

	freopen("length.in","r",stdin);

	freopen("length.out","w",stdout);

	scanf("%d",&n);

	R int f,v;

	for(R int i = 2;i <= n;++i)

	{

		f = rd();v = rd();

		add(i,f,v);

	}

	dfs1(1,1);dfs2(1,1);

	int x,y;

	x = BFS(1);y = BFS(x);

	BFS(1);

	for(int i = 1;i <= n;++i)

	{

		printf("%d\n",max(dist(i,x),dist(i,y)));

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}

Solution2：

其实可以树形 $DP$ ，先求一个子树中的最长链，然后再求一个从父亲来的最长链，可以先求一个 $maxf$ 表示子树中最长链，并记一下它来源于那棵子树，然后对于其他子树都可以用 $maxf+e[i].w$ 更新，对于这个子树，反正只有一个，可以再遍历一下其他所有子树再求一边最大值。

Code2：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 10010

struct edge

{

	int to,nxt,w;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].w = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].w = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool v[MAXN];

int f[MAXN],g[MAXN];

void dp1(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp1(e[i].to);

		f[k] = max(f[k],f[e[i].to] + e[i].w);

	}

	v[k] = false;

	return;

}

void dp2(int k)

{

	v[k] = true;

	int maxf = 0,bel,val;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		g[e[i].to] = g[k] + e[i].w;

		if(f[e[i].to] + e[i].w > maxf)

		{

			maxf = f[e[i].to] + e[i].w;

			bel = e[i].to;val = e[i].w;

		}

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		if(e[i].to != bel)

		{

			g[e[i].to] = max(g[e[i].to],maxf + e[i].w);

		}

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to] || e[i].to == bel)continue;

		g[bel] = max(g[bel],f[e[i].to] + e[i].w + val);

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp2(e[i].to);

	}

	v[k] = false;

	return;

}

int main()

{

	freopen("length.in","r",stdin);

	freopen("length.out","w",stdout);

	scanf("%d",&n);

	int fa,v;

	for(int i = 2;i <= n;++i)

	{

		scanf("%d%d",&fa,&v);

		add(i,fa,v);

	}

	dp1(1); 

	dp2(1);

	for(int i = 1;i <= n;++i)

	{

		printf("%d\n",max(f[i],g[i]));

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}