BZOJ 2152: 聪聪可可

点分治，每次维护出边长模3余0, 1, 2的个数
那么答案就是 $cnt[0] * cnt[0] + cnt[1] * cnt[2] * 2$
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define ll long long
  5 #define N 20010
  6 int n;
  7 int vis[N];
  8 struct Graph
  9 {
 10     struct node
 11     {
 12         int to, nx, w;
 13         node() {}
 14         node(int to, int nx, int w) : to(to), nx(nx), w(w) {}
 15     }a[N << 1];
 16     int head[N], pos;
 17     void init()
 18     {
 19         memset(head, 0, sizeof head);
 20         pos = 0;
 21     }
 22     void add(int u, int v, int w)
 23     {
 24         a[++pos] = node(v, head[u], w); head[u] = pos;
 25         a[++pos] = node(u, head[v], w); head[v] = pos;
 26     }
 27 }G;
 28 #define erp(u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w)
 29 
 30 int root, sum, sze[N], f[N];
 31 void getroot(int u, int fa)
 32 {
 33     sze[u] = 1, f[u] = 0;
 34     erp(u) if (v != fa && !vis[v]) 
 35     {
 36         getroot(v, u);
 37         sze[u] += sze[v];
 38         f[u] = max(f[u], sze[v]);
 39     }
 40     f[u] = max(f[u], sum - sze[u]);
 41     if (f[u] < f[root]) root = u;
 42 }
 43 
 44 ll d[N], cnt[3];
 45 void getdeep(int u, int fa)
 46 {
 47     ++cnt[d[u] % 3];
 48     erp(u) if (v != fa && !vis[v])
 49     {
 50         d[v] = d[u] + w;
 51         getdeep(v, u);  
 52     }
 53 }
 54 
 55 ll calc(int u, int cost)
 56 {
 57     d[u] = cost;
 58     memset(cnt, 0, sizeof cnt);
 59     getdeep(u, 0); 
 60     return cnt[0] * cnt[0] + cnt[1] * cnt[2] * 2; 
 61 }
 62 
 63 ll res;
 64 void solve(int u)  
 65 {
 66     res += calc(u, 0);
 67     vis[u] = 1;
 68     erp(u) if (!vis[v])
 69     {
 70         res -= calc(v, w);
 71         sum = f[0] = sze[v];
 72         root = 0;
 73         getroot(v, 0);
 74         solve(root);
 75     } 
 76 }
 77 
 78 ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
 79 void Run()
 80 {
 81     while (scanf("%d", &n) != EOF)
 82     {
 83         G.init(); res = 0;
 84         memset(vis, 0, sizeof vis);
 85         for (int i = 1, u, v, w; i < n; ++i)
 86         {
 87             scanf("%d%d%d", &u, &v, &w);
 88             G.add(u, v, w);
 89         }
 90         sum = f[0] = n; root = 0;
 91         getroot(1, 0);
 92         solve(root);
 93         ll a = res, b = 1ll * n * n; 
 94         ll GCD = gcd(a, b);
 95         a /= GCD, b /= GCD;
 96         printf("%lld/%lld
", a, b);
 97     }
 98 }
 99 
100 int main()
101 {
102     #ifdef LOCAL
103         freopen("Test.in", "r", stdin);
104     #endif 
105 
106     Run();
107     return 0;
108 }
View Code