【题目链接】 

 

【题目大意】

　　给出一棵树，问任取两点之间距离为3的倍数的概率是多少

 

【题解】

　　树分治统计模3之后不同的链长计算答案，最后和总数求个gcd化简即可。

 

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
          using namespace std;typedef pair
         
           P;#define ff first#define ss secondconst int N=20010;int n,cnt,ans,root,sum;int size[N],dp[N],d[N],t[5],vis[N];vector
          
 G[N];void add_edge(int u,int v,int w){ G[u].push_back(P(v,w)); G[v].push_back(P(u,w));}void getroot(int x,int fx){ size[x]=1; dp[x]=0; for(int i=0;i