B4016 20分求调
  • 板块B4016 树的直径
  • 楼主Nemuri
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/11 21:50
  • 上次更新2024/11/12 13:02:18
查看原帖
B4016 20分求调
1089862
Nemuri楼主2024/11/11 21:50
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
typedef long long int llint;
int M, N, K, T;
struct node
{
	vector<int> child;
	vector<int> mx;
	int m;
};
bool nf[MAXN];
int root;
node Node[MAXN];
bool cmp(int x, int y)
{
	return x > y;
}
int ans = 0;
int dfs(int p)
{
	vector<int> tmp = {0, 0};
	for(int i=0;i<Node[p].child.size();i++)
	{
		tmp.push_back(dfs(Node[p].child[i])+1);
	}
	sort(tmp.begin(), tmp.end(), cmp);
	ans = max(ans, tmp[0]+tmp[1]);
	return tmp[0];
}
int main()
{
	cin>>N;
	for(int i=1;i<N;i++)
	{
		int x, y;
		cin>>x>>y;
		nf[y] = 1;
		Node[x].child.push_back(y);	
	}
	for(int i=1;i<=N;i++)
	{
		if(!nf[i])
		{
			root = i;
		}
	}
	dfs(root);
	cout<<ans<<endl;
	return 0;
}

2024/11/11 21:50
加载中...