点分治常规题。练习模板
//OJ 2077 //by Cydiater //2016.9.23 #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <ctime> #include <cmath> #include <iomanip> #include <cstdlib> using namespace std; #define ll long long #define up(i,j,n) for(int i=j;i<=n;i++) #define down(i,j,n) for(int i=j;i>=n;i--) const int MAXN=1e6+5; const int oo=0x3f3f3f3f; inline int read(){ char ch=getchar();int x=0,f=1; while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int LINK[MAXN],len=0,sum,max_siz[MAXN],root,siz[MAXN],dis[MAXN],head,tail,q[MAXN],cnt[3],ans=0; bool vis[MAXN]; struct edge{ int y,next,v; }e[MAXN<<1]; int N; namespace solution{ inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;} inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);} void init(){ N=read(); memset(vis,0,sizeof(vis)); up(i,2,N){ int x=read(),y=read(),v=read(); insert(x,y,v); insert(y,x,v); } } void make_root(int node,int fa){ max_siz[node]=0;siz[node]=1; for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){ make_root(e[i].y,node); siz[node]+=siz[e[i].y]; max_siz[node]=max(max_siz[node],siz[e[i].y]); } max_siz[node]=max(max_siz[node],sum-max_siz[node]); if(max_siz[node]<max_siz[root])root=node; } void get_deep(int node,int fa){ q[++tail]=dis[node]; for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa&&!vis[e[i].y]){ dis[e[i].y]=dis[node]+e[i].v; get_deep(e[i].y,node); } } int col(int node,int dist){ dis[node]=dist;head=1;tail=0; get_deep(node,0); cnt[0]=cnt[1]=cnt[2]=0; up(i,head,tail)cnt[q[i]%3]++; return cnt[0]*cnt[0]+2*cnt[1]*cnt[2]; } void work(int node){ ans+=col(node,0); vis[node]=1; for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){ ans-=col(e[i].y,e[i].v); root=0; make_root(e[i].y,node); work(root); } } void slove(){ sum=N;max_siz[0]=oo;root=0; make_root(1,0); work(root); } void output(){ int d=gcd(ans,N*N); printf("%d/%d\n",ans/d,N*N/d); } } int main(){ //freopen("input.in","r",stdin); using namespace solution; init(); slove(); output(); return 0; }