bzoj 3124: [Sdoi2013]直径

时间:2022-09-12 06:13:52
 #include<cstdio>
#include<iostream>
#define M 400009
#define ll long long
using namespace std;
ll d[M],v[M],ans1;
int n,cnt=,head[M],next[M],u[M],mx,f[M],q[M],ans,mx1,fro[M],from[M],sum[M];
void jia(int a1,int a2,int a3)
{
cnt++;
from[cnt]=a1;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
v[cnt]=(ll)(a3)*(ll)(n);
return;
}
void bfs(int a1)
{
d[a1]=;
int h=,t=;
q[]=a1;
f[a1]=;
fro[a1]=;
sum[a1]=;
for(;h<t;)
{
int p=q[++h];
for(int i=head[p];i;i=next[i])
if(!f[u[i]])
{
f[u[i]]=;
q[++t]=u[i];
d[u[i]]=d[p]+v[i];
fro[u[i]]=i;
sum[u[i]]=sum[p]+;
}
}
return;
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int a1,a2,a3;
scanf("%d%d%d",&a1,&a2,&a3);
jia(a1,a2,a3);
jia(a2,a1,a3);
}
bfs();
ll max1=;
for(int i=;i<=n;i++)
{
if(max1<d[i])
{
max1=d[i];
mx1=i;
}
f[i]=;
}
bfs(mx1);
max1=;
for(int i=;i<=n;i++)
{
if(max1<d[i])
{
max1=d[i];
ans=i;
}
f[i]=;
}
ans1=d[ans];
printf("%lld\n",d[ans]/n);
for(;ans;)
{
int p=fro[ans];
v[p]--;
v[p^]--;
ans=from[p];
}
bfs();
max1=;
for(int i=;i<=n;i++)
{
if(max1<d[i])
{
max1=d[i];
mx1=i;
}
f[i]=;
}
bfs(mx1);
max1=;
for(int i=;i<=n;i++)
if(max1<d[i])
{
max1=d[i];
ans=i;
}
printf("%lld\n",ans1-d[ans]);
return ;
}

先找一条直径,把直径上的边的权值减去1,再找一遍直径,差便是答案。