30分蒟蒻改成了20分。。。大佬康康
查看原帖
30分蒟蒻改成了20分。。。大佬康康
189774
氢离子已超标楼主2020/7/22 09:45
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,x,y,cnt=0;
int head[1005];
int depth=0,wid[1002]={0},width=0,depp1=0,depp2=0;
struct node
{
	int d,fa;
}e[500005];
void dfs(int u,int fa)
{
	e[u].d=e[fa].d+1;
	if(e[u].d>depth) 
		depth=e[u].d;
	wid[e[u].d]++;
}
void LCA(int a,int b)
{
	if(e[b].d>e[a].d) 
	{
		depp2++;
		b=e[b].fa;
		LCA(a,b);
	}
	if(e[a].d>e[b].d) 
	{
		depp2++;
		a=e[a].fa;
		LCA(a,b);
	}
	if(e[a].d==e[b].d&&e[a].fa!=e[b].fa)
	{
		depp1++,depp2++;
		a=e[a].fa,b=e[b].fa;
	}
	if(e[a].fa==e[b].fa)
		return;
}
int main()
{
	memset(e,0,sizeof(e));
	int u,v;
	cin>>n;
	e[1].d=1;
	for(int i=1;i<=n-1;i++)
	{
		cin>>x>>y;
		e[y].fa=x;
		dfs(y,x);
	}
	cin>>u>>v;
	for(int i=1;i<=depth;i++)
		width=max(width,wid[i]);
	cout<<depth<<endl<<width<<endl;
	if(u==v) 
	{
		cout<<0;
		return 0;
	}
	if(e[u].fa==v) {cout<<2;return 0;}
	if(e[v].fa==u) {cout<<1;return 0;}
	LCA(u,v);
	cout<<depp2*2+depp1;
	return 0;
}

2020/7/22 09:45
加载中...