@Junlier
2018-08-21T17:16:04.000000Z
字数 1757
阅读 1838
图论——点分治
洛谷题目
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 20050
using namespace std;
const int Inf=1e9;
int n,cnt,ans;
int Max,tot,root;
struct EDGE{
int to,nxt,v;
}ljl[N<<1];
int hd[N];
int size[N],vis[N];
int dis[N],hh[3];
il int read()
{
rg int s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
il void add(rg int p,rg int q,rg int o)
{
ljl[++cnt]=(EDGE){q,hd[p],o},hd[p]=cnt;
}
void get_root(rg int now,rg int fm)
{
size[now]=1;rg int num=0;
for(rg int i=hd[now];i;i=ljl[i].nxt)
{
rg int qw=ljl[i].to;
if(qw==fm||vis[qw])continue;
get_root(qw,now);
size[now]+=size[qw];
num=max(num,size[qw]);
}
num=max(num,tot-size[now]);
if(Max>num)Max=num,root=now;
}
void get_dis(rg int now,rg int fm)
{
hh[dis[now]%3]++;
for(rg int i=hd[now];i;i=ljl[i].nxt)
{
rg int qw=ljl[i].to;
if(qw==fm||vis[qw])continue;
dis[qw]=dis[now]+ljl[i].v;
get_dis(qw,now);
}
}
il int Query(rg int now,rg int base)
{
rg int res=0;
hh[0]=hh[1]=hh[2]=0;
dis[now]=base;
get_dis(now,0);
res+=hh[0]*hh[0]+(hh[1]*hh[2]<<1);
return res;
}
void divide(rg int now,rg int fm)
{
ans+=Query(now,0),vis[now]=1;
rg int all=tot;
for(rg int i=hd[now];i;i=ljl[i].nxt)
{
rg int qw=ljl[i].to;
if(qw==fm||vis[qw])continue;
ans-=Query(qw,ljl[i].v);
tot=size[now]>size[qw]?size[qw]:all-size[qw];
root=0,Max=Inf;
get_root(qw,0);
divide(root,0);
}
}
il int gcd(rg int x,rg int y)
{
return y?gcd(y,x%y):x;
}
int main()
{
n=read();
for(rg int i=1;i<n;++i)
{
rg int p=read(),q=read(),o=read();
add(p,q,o),add(q,p,o);
}
Max=Inf,tot=n;
get_root(1,0),divide(root,0);
rg int GCD=gcd(ans,n*n);
printf("%d/%d\n",ans/GCD,n*n/GCD);
return 0;
}