求助,求树的直径的长度
  • 板块灌水区
  • 楼主Butterfly__qwq
  • 当前回复15
  • 已保存回复15
  • 发布时间2022/4/27 17:22
  • 上次更新2023/10/28 02:48:12
查看原帖
求助,求树的直径的长度
529038
Butterfly__qwq楼主2022/4/27 17:22

rt,

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define float double
#define mian main
#define ture true
int tree[(int)1e6+1];
int read()
{
    int x=0,f=1;
	char ch=getchar();
    while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
    while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
    return x*f;
}
int deep(int w,int d,int g)
{
	if(w==g)return d;
	return deep(tree[w],d+1,0);
}
int lca(int l1,int l2)
{
	while(l1!=l2)
	{
		if(deep(l1,0,0)>deep(l2,0,0))l1=tree[l1];
		else l2=tree[l2];
		if(l1==0||l2==0)return 0;
	}
    return l1;
}
signed main()
{
	int n,mxd=-1,id,mx=-1;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>tree[i];
		if(mxd<deep(tree[i],0,0))
		{
			mxd=deep(tree[i],0,0);
			id=i;
		}
	}
	int f=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(tree[j]==i)
			{
				f=1;
				break;
			}
		}
		if(f==0)
			if(mx<(deep(i,0,lca(i,id))+deep(id,0,lca(i,id))))mx=deep(i,0,lca(i,id))+deep(id,0,lca(i,id));
	}
	cout<<mx;
	return 0;
}
2022/4/27 17:22
加载中...