来看下面的数据
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&<>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&<>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&<==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
所以,数据应该加强了