话说今天这个1个同学2002的题目真的有可总结性吗。
今天的结论是我的暴力又进化了，现在可以长达5KB，一节更比六节强。明天再来听评讲。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct edge
{
long long to,d;
edge* next;
};
edge* head[5002],v[10004];
long long ne=0,n,x,y,w,s,n1,n2;
long long ca[5002][15],si1[5002],si2[5002],divv[5002];
long long de[5002],di[5002];
bool in[5002];
void ad(long long a,long long b,long long c)
{
v[ne].to=b;
v[ne].d=c;
v[ne].next=head[a];
head[a]=&v[ne];
ne++;
}
void ss1(long long p)
{
in[p]=true;
divv[p]=1;
n1++;
si1[p]=1;
for (edge* z=head[p];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false)
{
ss1(z->to);
si1[p]+=si1[z->to];
}
}
return;
}
void ss2(long long q)
{
in[q]=true;
divv[q]=2;
n2++;
si2[q]=1;
for (edge* z=head[q];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false)
{
ss2(z->to);
si2[q]+=si2[z->to];
}
}
return;
}
void dfs1(long long p)
{
in[p]=true;
for (edge* z=head[p];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false)
{
de[z->to]=de[p]+1;
di[z->to]=di[p]+z->d;
dfs1(z->to);
ca[z->to][0]=p;
}
}
return;
}
void dfs2(long long q)
{
in[q]=true;
for (edge* z=head[q];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false)
{
de[z->to]=de[q]+1;
di[z->to]=di[q]+z->d;
dfs2(z->to);
ca[z->to][0]=q;
}
}
return;
}
long long lca(long long g,long long h)
{
long long k;
if (de[g]>de[h])
{
k=g;
g=h;
h=k;
}
for (int i=14;i>=0;i--)
{
if (de[ca[h][i]]>=de[g])
{
h=ca[h][i];
}
}
if (g==h) return h;
for (int i=14;i>=0;i--)
{
if (ca[g][i]!=ca[h][i])
{
g=ca[g][i];
h=ca[h][i];
}
}
return ca[h][0];
}
long long gogogo(long long p,long long q,long long y)
{
long long ans=0;
n1=0;
n2=0;
memset(ca,0,sizeof(ca));
memset(si1,0,sizeof(si1));
memset(si2,0,sizeof(si2));
memset(divv,0,sizeof(divv));
memset(in,false,sizeof(in));
divv[p]=1;
divv[q]=2;
ss1(p);
ss2(q);
long long t1=0,o1=p,t2=0,o2=q;
memset(in,false,sizeof(in));
in[p]=true;
in[q]=true;
for (edge* z=head[p];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false && si1[z->to]>t1)
{
t1=si1[z->to];
o1=z->to;
}
if (z->to!=-1) in[z->to]=true;
}
while (2*t1>n1 && n1!=1)
{
p=o1;
t1=0;
for (edge* z=head[p];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false && si1[z->to]>t1)
{
t1=si1[z->to];
o1=z->to;
}
if (z->to!=-1) in[z->to]=true;
}
}
for (edge* z=head[q];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false && si2[z->to]>t2)
{
t2=si2[z->to];
o2=z->to;
}
if (z->to!=-1) in[z->to]=true;
}
while (2*t2>n2 && n2!=1)
{
q=o2;
t2=0;
for (edge* z=head[q];z!=NULL;z=z->next)
{
if (z->to!=-1 && in[z->to]==false && si2[z->to]>t1)
{
t2=si2[z->to];
o2=z->to;
}
if (z->to!=-1) in[z->to]=true;
}
}
for (long long i=0;i<15;i++)
{
ca[p][i]=0;
ca[q][i]=0;
}
memset(di,0,sizeof(di));
memset(de,0,sizeof(de));
memset(in,false,sizeof(in));
dfs1(p);
dfs2(q);
for (long long i=1;i<15;i++)
{
for (long long j=1;j<=n;j++)
{
ca[j][i]=ca[ca[j][i-1]][i-1];
}
}
long long u1=0,u2=0;
for (long long i=1;i<n;i++)
{
for (long long j=i+1;j<=n;j++)
{
if (divv[i]==1 && divv[j]==1)
{
u1+=di[i]+di[j]-2*di[lca(i,j)];
}
}
}
for (long long i=1;i<n;i++)
{
for (long long j=i+1;j<=n;j++)
{
if (divv[i]==2 && divv[j]==2)
{
u2+=di[i]+di[j]-2*di[lca(i,j)];
}
}
}
ans+=n1*n2*y+u1+u2;
u1=0;
u2=0;
for (long long i=1;i<=n;i++)
{
if (divv[i]==1)
{
u1+=di[i];
}
else
{
u2+=di[i];
}
}
ans+=n1*u2+n2*u1;
return ans;
}
int main()
{
freopen("testA.in","r",stdin);
freopen("testA.out","w",stdout);
cin>>n;
for (long long i=0;i<=n;i++)
{
head[i]=NULL;
}
for (long long i=1;i<n;i++)
{
cin>>x>>y>>w;
ad(x,y,w);
ad(y,x,w);
}
s=1000000000000000;
for (long long i=1;i<n;i++)
{
long long l,r;
r=v[i*2-2].to;
l=v[i*2-1].to;
v[i*2-2].to=-1;
v[i*2-1].to=-1;
s=min(s,gogogo(l,r,v[i*2-2].d));
v[i*2-2].to=r;
v[i*2-1].to=l;
}
cout<<s;
return 0;
}
暴得一手好力