DP实现树的直径 模板一直WA 求大佬找错qwq
  • 板块学术版
  • 楼主西卡洛斯
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/1/21 23:14
  • 上次更新2023/11/5 04:34:37
查看原帖
DP实现树的直径 模板一直WA 求大佬找错qwq
240165
西卡洛斯楼主2021/1/21 23:14
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int maxDistance=0;
vector<int> G[100001];
inline void AddEdge(int v,int s)
{
	G[v].push_back(s);
	G[s].push_back(v);
}

int LastOrder(int pre,int cur)//cur当前节点,pre为cur的父节点 
{
	int first=0,second=0;//最大值和次大值 
	for(int i=0;i<G[cur].size();++i)//枚举cur的没一个子节点 
	{
		if(G[cur][i]==pre) continue;//一直向下,不找重复的边 
		int temp=LastOrder(cur,G[cur][i]);//向下找 
		if(temp>first)
		{
			second=first;
			first=temp;
		}
		else if(temp>second) second=temp;
		maxDistance=max(maxDistance,first+second);
		return first+1;//返回当前子树最大深度 
	}
}

int main()
{
	int N;
	scanf("%d",&N);
	int Ai,Bi;
	for(int i=1;i<N;++i)
	{
		scanf("%d%d",&Ai,&Bi);
		AddEdge(Ai,Bi);
	}
	LastOrder(0,1);
	printf("%d",maxDistance);
	return 0;
}
2021/1/21 23:14
加载中...