P2634 [国家集训队]聪聪可可

淀粉质

第二道点分治的题

关于点分治的一点理解：

所谓点分治，其实就是把要求的问题(一般与路径有关)划分成两种情况

1.路径经过rt(根节点)

2.路径在根节点的子树内

我们只需要处理情况1,因为情况2就是情况1的递归子问题

在这个过程中,要注意容斥原理的应用;

//--------------------------------------------------------------------------

关于此题:

w可预先%3(不会影响答案),注意乘法原理的应用;

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 #define up(i,l,r) for(register int i = (l); i <= (r); ++i)

 #define dn(i,l,r) for(register int i = (l); i >= (r); --i)

 #define ll long long

 #define re register

 using namespace std;

 template <typename T> void in(T &x) {

     x = ; T f = ; char ch = getchar();

     while(!isdigit(ch)) {if(ch == '-') f = -; ch = getchar();}

     while( isdigit(ch)) {x =  * x + ch - ; ch = getchar();}

     x *= f;

 }

 template <typename T> void out(T x) {

     if(x < ) x = -x , putchar('-');

     if(x > ) out(x/);

     putchar(x% + );

 }

 //---------------------------------------------------------

 const int N = ;

 int n;

 ll ans = ;

 struct edge {

     int v,w,nxt;

 }e[N<<];int tot,head[N];

 void add(int u,int v,int w) {

     e[++tot].v = v;

     e[tot].w = w;

     e[tot].nxt = head[u];

     head[u] = tot;

 }

 //---------------------------------------------------------

 bool vis[N];

 int size[N],f[N];

 int Tsize,rt,dis[N];

 int t[];

 void get_rt(int u,int fa) {

     size[u] = ; f[u] = ;

     for(re int i = head[u]; i ;i = e[i].nxt) {

         int v = e[i].v; if(v == fa || vis[v]) continue;

         get_rt(v,u); size[u] += size[v];

         f[u] = max(f[u],size[v]);

     }

     f[u] = max(f[u],Tsize-size[u]);

     if(f[u] < f[rt]) rt = u;

 }

 void get_dis(int u,int fa) {

     ++t[dis[u]%];

     for(re int i = head[u]; i ;i = e[i].nxt) {

         int v = e[i].v; if(v == fa || vis[v]) continue;

         dis[v] = (dis[u]+e[i].w)%; get_dis(v,u);

     }

 }

 ll calc(int u) {

     t[] = t[] = t[] = ;

     get_dis(u,);

     return t[]*t[]+*t[]*t[];

 }

 void solve(int u) {

     vis[u] = ; dis[u] = ;

     ans += calc(u);

     for(re int i = head[u]; i ;i = e[i].nxt) {

         int v = e[i].v; if(vis[v]) continue;

         dis[v] = e[i].w;

         ans -= calc(v);

         Tsize = size[v],rt = ,f[] = n+;

         get_rt(v,); solve(rt);

     }

 }

 void init() {

     memset(head,,sizeof(head));

     memset(vis,,sizeof(vis));

     ans = ; Tsize = n,rt = ,f[] = n+;

 }

 ll Gcd(ll a,ll b) {return b ==  ? a:Gcd(b,a%b);}

 int main() {

     init();

     in(n); int x,y,w;

     up(i,,n-) {

         in(x); in(y); in(w); add(x,y,w%),add(y,x,w%);

         //技巧 mod 3

     }

     get_rt(,); solve(rt);

     ll gcd = Gcd(ans,1ll*n*n);

     out(ans/gcd); putchar('/'); out(1ll*n*n/gcd);

     return ;

 }