题意：

　　给你一棵树，问任选两个点（x,y）满足x到y的树上距离是3的倍数的概率。

题解：

　　只要求出一共有多少个点对（x,y）满足x到y的树上距离为3的倍数即可。

　　那么怎么求呢？点分治。

　　什么是点分治呢？

　　就是先找到树的重心（就是以它为根时最大子树大小最小的节点），把它定为根，然后求经过根的路径条数有多少。再递归求每个子树节点即可。复杂度O（n*logn）。

　　为什么要用点分治呢？

　　因为点分治可以保证最坏复杂度为O（n*logn）。具体证明有兴趣的同学可以百度一下。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define LL long long
 5 #define RI register int
 6 using namespace std;
 7 const int INF = 0x7ffffff ;
 8 const int N = 20000 + 10 ;
 9 
10 inline int read() {
11     int k = 0 , f = 1 ; char c = getchar() ;
12     for( ; !isdigit(c) ; c = getchar())
13       if(c == '-') f = -1 ;
14     for( ; isdigit(c) ; c = getchar())
15       k = k*10 + c-'0' ;
16     return k*f ;
17 }
18 struct Edge {
19     int to, next, val ;
20 }e[N<<1] ;
21 int n, root, ans = 0, sum ; int head[N], siz[N], dep[N], t[5], f[N] ;
22 bool vis[N] ;
23 inline void add_edge(int x,int y,int z) {
24     static int cnt = 0 ;
25     e[++cnt].to = y, e[cnt].val = z, e[cnt].next = head[x], head[x] = cnt ;
26 }
27 
28 void get_deep(int x,int fa) {
29     t[dep[x]] ++ ;
30     for(int i=head[x];i;i=e[i].next) {
31         int y = e[i].to ;
32         if(y == fa || vis[y]) continue ;
33         dep[y] = (dep[x] + e[i].val)%3 ;
34         get_deep(y,x) ;
35     }
36 }
37 inline int calc(int x,int deep) {
38     t[0] = t[1] = t[2] = 0 ;
39     dep[x] = deep ;
40     get_deep(x,0) ;
41     return t[1]*t[2]*2 + t[0]*t[0] ;
42 }
43 void get_root(int x,int fa) {
44     siz[x] = 1 ; f[x] = 0 ;
45     for(int i=head[x];i;i=e[i].next) {
46         int y = e[i].to ;
47         if(y == fa || vis[y]) continue ;
48         get_root(y,x) ; siz[x] += siz[y] ;
49         f[x] = max(f[x],siz[y]) ;
50     }
51     f[x] = max(f[x],sum-siz[x]) ;
52     if(f[x] < f[root]) root = x ;
53 }
54 void solve(int x) {
55     ans += calc(x,0) ;
56     vis[x] = 1 ;
57     for(int i=head[x];i;i=e[i].next) {
58         int y = e[i].to ;
59         if(vis[y]) continue ;
60         ans -= calc(y,e[i].val) ; // 
61         root = 0 ; sum = siz[y] ; 
62         get_root(y,0) ;
63         solve(root) ;
64     }
65 }
66 
67 int gcd(int a,int b) { return b == 0 ? a : gcd(b,a%b) ; }
68 int main() {
69     n = read() ;
70     int x, y, z ;
71     for(int i=1;i<n;i++) {
72         x = read(), y = read(), z = read()%3 ;
73         add_edge(x,y,z) ; add_edge(y,x,z) ;
74     }
75     sum = f[0] = n ; root = 0 ;
76     get_root(1,0) ;
77     solve(root) ;
78     int fm = n*n ;
79     int gg = gcd(fm,ans) ; 
80     printf("%d/%d",ans/gg,fm/gg) ;
81     return 0 ;
82 }

View Code

——end ;