题目链接：

 

  题意：

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

 

  题解：

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

　　那么怎么求呢？点分治。

　　什么是点分治呢？

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

　　为什么要用点分治呢？

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

 

 

1 #include
      
        2 #include
       
         3 #include
        
          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
        
       
      

 

 ——end ;