数据应该加强一下
查看原帖
数据应该加强一下
211536
李宇涵楼主2022/7/2 19:06

来看下面的数据

4
1 2 1
1 3 1
1 4 1

是一个星型图,直径长度为2,没有任何一条边被所有直径经过(直径是2-1-3时不经过1-4,直径是2-1-4时不经过1-3,直径是3-1-4时不经过1-2),因此答案应该为:

2
0

但是用下面代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p1,p2,max1,max2,ans1,ans2,ansm,cnt,d[200020],l[200020],suml,hd,mp1,mp2,tl1,tl2,se[200020],sm;
bool b3,ty;
struct edge{int len,v;};
vector <edge> e[200020];
void dfs1(int u,int fa,int lt)
{
	bool b;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i].v;
		if(v==fa) continue;
		b=1;
		dfs1(v,u,lt+e[u][i].len);
	}
	if(!b&&lt>max1)
	{
		max1=lt;
		p1=u;
	}
}
void dfs2(int u,int fa,int lt)
{
	bool b;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i].v;
		if(v==fa) continue;
		b=1;
		dfs2(v,u,lt+e[u][i].len);
	}
	if(!b&&lt>max2)
	{
		max2=lt;
		p2=u;
	}
}
void getd(int u,int fa,int p)
{
	if(u==p) 
	{
		b3=1;
		return;
	}
	for(int i=0;i<e[u].size();i++)
	{
		if(b3) return;
		int v=e[u][i].v;
		if(v==fa) continue;
		getd(v,u,p);
		if(b3)
		{
			d[++cnt]=v;
			l[cnt+1]=e[u][i].len;
			return;
		}
	}
}
int dfsp(int u,int fa,int lt,int tl)
{
	int sume=0;
	bool b=0;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i].v;
		if(v==fa) continue;
		b=1;
		sume+=dfsp(v,u,lt+e[u][i].len,tl);
	}
	if(!b&&lt==tl) sume=1;
	se[u]=sume;
	return sume;
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n-1;i++)
	{
		int t1,t2,t3;
		scanf("%lld%lld%lld",&t1,&t2,&t3);
		edge e1,e2;
		e1.len=e2.len=t3;
		e1.v=t1;
		e2.v=t2;
		e[t1].push_back(e2);
		e[t2].push_back(e1);
	}
	dfs1(1,-1,0);
	dfs2(p1,-1,0);
	ans1=max2;
	getd(p2,-1,p1);
	d[++cnt]=p2;
	int hd=ans1/2;
	for(int i=1;i<=cnt;i++)
	{
		suml+=l[i];
		if((ans1%2==0)&&suml==hd)
		{
			ty=1;
			mp1=d[i];
			break;
		}
		if(suml>hd)
		{
			mp1=d[i-1];
			mp2=d[i];
			tl1=suml-l[i];
			tl2=ans1-suml;
			break;
		}
	}
	if(ty)
	{
		for(int i=0;i<e[mp1].size();i++)
		{
			sm=dfsp(e[mp1][i].v,mp1,0,hd-1);
			if(!sm) continue;
			for(int i=1;i<=n;i++)
			{
				if(se[i]==sm)
				{
					ans2++;
				}
			}
			memset(se,0,sizeof(se));
		}
	}
	else
	{
		sm=dfsp(mp1,mp2,0,tl1);
		for(int i=1;i<=n;i++)
		{
			if(se[i]==sm) ans2++;
		}
		memset(se,0,sizeof(se));
		sm=dfsp(mp2,mp1,0,tl2);
		for(int i=1;i<=n;i++)
		{
			if(se[i]==sm) ans2++;
		}
		ans2--;
	}
	printf("%lld\n%lld",ans1,ans2);
    return 0;
}

得到的结果是:

2
3

所以,数据应该加强了

2022/7/2 19:06
加载中...