过样例0pts求助
查看原帖
过样例0pts求助
1011279
Naoxiaoyu楼主2024/7/6 16:47
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MX=200000;
int n,cnt=0,root;
ll len=0;
int h[MX+10],vis[MX+10];
int last[MX+10],nexta[MX+10];
ll dis[MX+10],lon[MX+10];
struct Edge{
	int v,w,nxt;
}e[(MX<<1)+10];
void add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=h[u];
	h[u]=cnt;
}
void dfs1(int x,int fa,ll p)
{
	if(p>len)
	{
		len=p;
		root=x;
	}
	vis[x]=1;
	for(int i=h[x];i;i=e[i].nxt)
	{
		int y=e[i].v,wei=e[i].w;
		if(!vis[y]) dfs1(y,x,p+wei);
	}
}
void dfs2(int x,int fa,ll p)
{
	last[x]=fa;
	lon[x]=p;
	if(p>len)
	{
		len=p;
		root=x;
	}
	vis[x]=1;
	for(int i=h[x];i;i=e[i].nxt)
	{
		int y=e[i].v,wei=e[i].w;
		if(!vis[y]) dfs2(y,x,p+wei);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);
		add(y,x,w);
	}
	dfs1(1,0,0);
	memset(vis,0,sizeof(vis));
	len=0;
	dfs2(root,0,0);
	memset(vis,0,sizeof(vis));
	printf("%lld\n",len);
	int f=0;
	for(int i=root;i;i=last[i])
	{
		vis[i]=1;
		nexta[i]=f;
		f=i;
	}//
//	for(int i=root;i;i=last[i])
//	{
//		printf("%d ",i);
//	}
//	printf("\n");
//	printf("%d %d\n",root,f);
//	for(int i=f;i;i=nexta[i])
//	{
//		printf("%d ",i);
//	}
//	printf("\n");
	for(int i=root;i;i=last[i])
	{
		len=0;
		dfs1(i,0,0);
		dis[i]=len;
	}
	int i,ans=0;
	for(i=f;i;i=nexta[i])
	{
		if(lon[root]-lon[i]==dis[i]) break;
	}
	for(;i;i=last[i])
	{
		if(lon[i]==dis[i]) break;
		ans++;
	}
	printf("%d\n",ans);
	return 0;
}
2024/7/6 16:47
加载中...