M_sea

洛谷2634 [国家集训队]聪聪可可
题目描述聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电...
扫描右侧二维码阅读全文
16
2018/08

洛谷2634 [国家集训队]聪聪可可

题目描述

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况下石头剪刀布就好了,可是他们已经玩儿腻了这种低智商的游戏。

他们的爸爸快被他们的争吵烦死了,所以他发明了一个新游戏:由爸爸在纸上画n个“点”,并用n-1条“边”把这n个“点”恰好连通(其实这就是一棵树)。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点(当然他们选点时是看不到这棵树的),如果两个点之间所有边上数的和加起来恰好是3的倍数,则判聪聪赢,否则可可赢。

聪聪非常爱思考问题,在每次游戏后都会仔细研究这棵树,希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

传送门

算法

点分治板子。

设$t[i]$表示模3为$i$的方案数。

那么当前的贡献为$t[0]*t[0]+2*t[1]*t[2]$。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n;

//邻接表 
struct Edge { int v,w,nxt; } e[40010];
int head[20010],cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++cnt].v=v; e[cnt].w=w;
    e[cnt].nxt=head[u]; head[u]=cnt;
}

//求重心 
int root,sum;
int f[20010],sz[20010];
bool vis[20010];

inline void getroot(int u,int fa) {
    sz[u]=1; f[u]=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (v==fa||vis[v]) continue;
        getroot(v,u); sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }
    f[u]=max(f[u],sum-sz[u]);
    if (f[u]<f[root]) root=u;
}

int t[3],dep[20010];

//求深度 
inline void getdeep(int u,int fa) {
    t[dep[u]%3]++;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (v==fa||vis[v]) continue;
        dep[v]=dep[u]+w;
        getdeep(v,u);
    }
}

//点分治
int ans=0;

inline int calc(int u,int d0) {
    dep[u]=d0; t[0]=t[1]=t[2]=0;
    getdeep(u,0);
    return t[0]*t[0]+t[1]*t[2]*2;
}
inline void solve(int u) {
    ans+=calc(u,0); vis[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;
        if (vis[v]) continue;
        ans-=calc(v,w);
        sum=sz[v],root=0;
        getroot(v,0);
        solve(root);
    }
}

int main() {
    n=read();
    for (re int i=1;i<n;i++) {
        int a=read(),b=read(),c=read();
        addEdge(a,b,c);
        addEdge(b,a,c);
    }
    sum=f[0]=n;
    getroot(1,0);
    solve(root);
    int d=__gcd(ans,n*n);
    printf("%d/%d\n",ans/d,n*n/d);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 14 PM

发表评论