被所有直径经过的边的数量wa8个点求调
查看原帖
被所有直径经过的边的数量wa8个点求调
774592
Augensterm楼主2024/7/29 09:56
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int n;
int h[N],e[N*2],ne[N*2],w[N*2],idx;
int pre[N];
int num[N];
int rt1,rt2,q[N];
LL dist[N];
bool vis[N];
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c;ne[idx]=h[a],h[a]=idx++;
	return;
} 
void bfs(int st)
{
 	memset(vis,0,sizeof vis);
 	dist[st]=0;vis[st]=1;
 	int hh=0,tt=-1;
 	q[++tt]=st;
 	while(hh<=tt)
 	{
 		int t=q[hh++];
 		for(int i=h[t];~i;i=ne[i])
 		{
 			int j=e[i];
			if(vis[j])continue;
			dist[j]=dist[t]+w[i];
			vis[j]=1;pre[j]=t;
			q[++tt]=j;
		 }
	 }
	return;
}
LL dfs(int u,int fa)
{
	LL s=0;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j==fa||vis[j])continue;
		s=max(s,dfs(j,u)+w[i]);
	}
	return s;
}
int main()
{
	scanf("%d",&n);
	memset(h,-1,sizeof h);
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	LL s=0;
	int x,l,r;
	bfs(1);
	for(int i=1;i<=n;i++)
		if(dist[i]>s)s=dist[1],rt1=i;
	bfs(rt1);
	s=0;
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++)
		if(dist[i]>s)s=dist[i],rt2=i;
	x=rt2,vis[rt1]=1;
	while(x!=rt1)
	{
		vis[x]=1;
		num[pre[x]]=num[x]+1;
		x=pre[x];
	}
	l==rt2,x=rt2,r=rt1;
	while(x!=rt1)
	{
		s=dfs(x,-1);
		if(s==dist[rt2]-dist[x])
			l=x;
		if(s==dist[x])
		{
			r=x;break;
		}
		x=pre[x];
	}
	printf("%lld\n%d",dist[rt2],num[r]-num[l]);
	return 0;
}
//  
2024/7/29 09:56
加载中...