http://www.lydsy.com/JudgeOnline/problem.php?id=1776

题意

一棵树，每个节点有一个编号，一共K种编号，输出每种编号的控制范围，即所有该编号的点，在树上的最远点对。

题解

对于每种编号，

最远点对中的其中一个点肯定离根最远，

所以先找出这个点，

枚举剩下的点，用lca算出每个点和找出的点的距离，更新答案即可。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;
const int N=200001,K=100001,M=N*2,Q=N*3;
int q[Q],d[N],num[N],p[N],Max[K],ans[N];
int v[M],next[M],head[N],k;
int n,m;

struct SegmentTree
{
	int m[Q*3];
	void update(int x)
	{
		int l=x<<1,r=l+1;
		m[x]=m[l];
		if(d[m[x]]>d[m[r]])
			m[x]=m[r];
	}
	void build(int x,int s,int t)
	{
		if(s==t)
		{
			m[x]=q[s];return;
		}
		int mid=s+t>>1;
		build(x<<1,s,mid);build((x<<1)+1,mid+1,t);
		update(x);
	}
	int get(int x,int s,int t,int ll,int rr)
	{
		if(ll<=s&&t<=rr)	return m[x];
		int t1=0,t2=0,mid=s+t>>1;
		if(ll<=mid)	t1=get(x<<1,s,mid,ll,rr);
		if(rr>mid)	t2=get((x<<1)+1,mid+1,t,ll,rr);
		if(d[t1]<d[t2])	return t1;
		else return t2;
	}
}a;
void add(int x,int y)
{
	if((!x)||(!y))	return;
	v[++k]=y;next[k]=head[x];head[x]=k;
}
void dfs(int x,int fa,int deep)
{
	q[++q[0]]=x;num[x]=q[0];d[x]=deep;
	if(d[x]>d[Max[p[x]]])	Max[p[x]]=x;
	for(int i=head[x];i;i=next[i])
		if(v[i]!=fa)
			dfs(v[i],x,deep+1),q[++q[0]]=x;
}
int lca(int x,int y)
{
	if(num[x]>num[y])	swap(x,y);
	return a.get(1,1,q[0],num[x],num[y]);
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",p+i,&x);
		add(x,i);add(i,x);
	}
	dfs(1,0,0);d[0]=INT_MAX;
	a.build(1,1,q[0]);
	for(int i=1;i<=n;i++)
	{
		int tmp=d[i]+d[Max[p[i]]]-d[lca(i,Max[p[i]])]*2;
		ans[p[i]]=max(ans[p[i]],tmp);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
}