来自FallDream的博客，未经允许，请勿转载， 谢谢。

---

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

n<=20000  0.3s

 

点分治练手题..

#include
     
      #include
      
       #define MN 20000#define INF 2000000000#define ll long longusing namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1;  ch = getchar();}    while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}    return x * f;}int n,head[MN+5],cnt=0,rt,mn,size[MN+5],tot,mx[MN+5],dep[MN+5],num[MN+5];struct edge{
   int to,next,w;}e[MN*2+5];bool b[MN+5];ll ans=0;inline void ins(int f,int t,int w){    e[++cnt]=(edge){t,head[f],w};head[f]=cnt;    e[++cnt]=(edge){f,head[t],w};head[t]=cnt;}void getrt(int x,int f){    for(int i=head[x];i;i=e[i].next)        if(!b[e[i].to]&&e[i].to!=f)            getrt(e[i].to,x);    int sz=max(mx[x],tot-size[x]);    if(sz
       
        mx[x]) mx[x]=size[e[i].to];        }}void solve(int x){    b[x]=1;dep[x]=0;int A=1,B=0,C=0;    for(int i=head[x];i;i=e[i].next)        if(!b[e[i].to])        {            num[0]=num[1]=num[2]=0;            dep[e[i].to]=e[i].w;dfs(e[i].to,x);            ans+=num[0]*A+num[1]*C+num[2]*B;            A+=num[0];B+=num[1];C+=num[2];        }    for(int i=head[x];i;i=e[i].next)        if(!b[e[i].to])        {            mn=INF;tot=size[e[i].to];            getrt(e[i].to,x);            solve(rt);        }}ll gcd(ll x,ll y){
    return !y?x:gcd(y,x%y);}int main(){    tot=n=read();    for(int i=1;i