比赛 4043级2023省选模拟赛3 评测结果 WWWAWWWTTT
题目名称 旅游 最终得分 10
用户昵称 遥时_彼方 运行时间 5.718 s
代码语言 C++ 内存使用 12.06 MiB
提交时间 2023-03-24 21:04:00
显示代码纯文本
#include<bits/stdc++.h>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define drep(x,y,z) for(int x=y;x>=z;x--)
#define ull unsigned long long
#define ll long long
using namespace std;
inline int read()
{
	int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
}
inline void write(int x)
{
	if(x<0) {x=~(x-1);putchar('-');}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
////////////////////////
const int N=2e5+50;
int nc;
map<pair<int,int>,int> g;
int hd[N];
struct T
{
	int ar;
	int nx;
}a[N<<1];
int aj;
inline void TADD(int x,int y)
{
	a[++aj].ar=y;
	a[aj].nx=hd[x];
	hd[x]=aj;
}
inline void ADD(int x,int y,int cl)
{
	if(x>y) swap(x,y);
	if(g[make_pair(x,y)]) TADD(g[make_pair(x,y)],cl),TADD(cl,g[make_pair(x,y)]);
	else g[make_pair(x,y)]=cl;
}
int j[N];
int l[N][2];
int dfs(int x)
{
	j[x]=1;
	for(int i=hd[x],o=0;i;i=a[i].nx)
	{
		if(j[a[i].ar]) continue;
		l[x][o]=dfs(a[i].ar);
		o++;
	}
	return max(l[x][0]+1,l[x][1]+1);
}
int ans;
void dfs0(int x,int con,int dep)
{
	if(!x) return;
	j[x]=1;
	ans=max(ans,max(dep+l[x][0]+con,dep+l[x][1]+con));
//	cout<<x<<":"<<ans<<endl;
	for(int i=hd[x];i;i=a[i].nx) if(!j[a[i].ar]) dfs0(a[i].ar,con,dep+1);
}
int main()
{
    freopen("journey.in","r",stdin);
	freopen("journey.out","w",stdout);
	nc=read();
	int s1,s2,s3;
	rep(i,1,nc-2)
	{
		s1=read(),s2=read(),s3=read();
		ADD(s1,s2,i),ADD(s2,s3,i),ADD(s1,s3,i);
	}
	s1=1;
	dfs(s1);
//	rep(i,1,nc)
//	{
//		cout<<i<<":"<<l[i][0]<<" "<<l[i][1]<<endl;
//	}
	memset(j,0,sizeof(j));
	j[s1]=1;
	dfs0(a[hd[s1]].ar,l[s1][1],1);
	memset(j,0,sizeof(j));
	j[s1]=1;
	dfs0(a[a[hd[s1]].nx].ar,l[s1][0],1);
	ans=max(ans,l[s1][0]+l[s1][1]);
	cout<<ans+1<<endl;
    return 0;
}