点分治傻逼题。。。直接DP就行了
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define LL long long using namespace std; const int maxx = 2e5+6; int ver[maxx],sz[maxx],Next[maxx],edge[maxx],head[maxx],mx[maxx]; int vis[maxx]; int dis[maxx]; int tot,ans,n,m,root,size; inline int read() { char ch = getchar(); int x = 0, f = 1; while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); } while('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int gcd(int a,int b){ return (!b)?a:gcd(b,a%b); } void add(int u,int v,int w){ ver[++tot]=v;edge[tot]=w;Next[tot]=head[u];head[u]=tot; ver[++tot]=u;edge[tot]=w;Next[tot]=head[v];head[v]=tot; } void getroot(int u,int fa){ sz[u]=1; mx[u]=0; for (int i=head[u];i;i=Next[i]){ int v=ver[i]; if (v==fa||vis[v])continue; getroot(v,u); sz[u]+=sz[v]; mx[u]=max(mx[u],sz[v]); } mx[u]=max(mx[u],size-mx[u]); if(!root||mx[u]<mx[root]){ root=u; } } void getdis(int u,int fa,int w){ dis[w%3]++; for (int i=head[u];i;i=Next[i]){ int v=ver[i]; if (v==fa || vis[v])continue; getdis(v,u,w+edge[i]); } } LL cal(int u,int w){ dis[0]=dis[1]=dis[2]=0; // dis[w%3]++; getdis(u,0,w); return dis[1]*dis[2]*2+dis[0]*dis[0]; } LL dfs(int u){ vis[u]=1; LL s=cal(u,0); ans+=s; for (int i=head[u];i;i=Next[i]){ int v=ver[i]; if (vis[v])continue; ans-=cal(v,edge[i]); root=0; size=sz[v]; getroot(v,0); dfs(root); } } int main(){ int u,v,w; n=read(); for (int i=1;i<n;i++){ u=read(); v=read(); w=read(); add(u,v,w); } ans=0; size=n; root=0; getroot(1,0); dfs(root); int gc=gcd(n*n,ans); printf("%d/%d ",ans/gc,n*n/gc); return 0; }