luogu2634

P2634 [国家集训队]聪聪可可

题目描述

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

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

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

输入格式

输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。

输出格式

以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。

输入输出样例

输入 #1

输出 #1

13/25

说明/提示

【样例说明】

13组点对分别是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。

【数据规模】

对于100%的数据，n<=20000。

sol：树形dp即可，也可以点分（很久前写的（大雾，dp[i][j]表示以i为根的子树中到i的和%i=j的个数

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0; bool f=0; char ch=' ';
    while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0) {putchar('-'); x=-x;}
    if(x<10) {putchar(x+'0'); return;}
    write(x/10); putchar((x%10)+'0');
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=20005,M=40005;
int n,dp[N][3],ans=0;
int tot=0,Next[M],to[M],val[M],head[N];
inline void Link(int x,int y,int z){Next[++tot]=head[x]; to[tot]=y; val[tot]=z; head[x]=tot;}
inline void dfs(int x,int fat)
{
    int e,i,j;
    dp[x][0]=1; dp[x][1]=dp[x][2]=0;
    for(e=head[x];e;e=Next[e]) if(to[e]!=fat)
    {
        dfs(to[e],x);
        for(i=0;i<3;i++)
        {
            ans+=dp[x][i]*dp[to[e]][(6-i-val[e])%3]*2;
        }
        for(i=0;i<3;i++)
        {
            dp[x][(i+val[e])%3]+=dp[to[e]][i];
        }
    }
//    cout<<x<<' '<<dp[x][0]<<' '<<dp[x][1]<<' '<<dp[x][2]<<endl;
}
int main()
{
    int i,x,y,z;
    R(n);
    for(i=1;i<n;i++)
    {
        R(x); R(y); z=read()%3; Link(x,y,z); Link(y,x,z);
    }
    dfs(1,0);
    ans+=n;
    int gg=__gcd(n*n,ans);
    write(ans/gg); putchar('/'); Wl(n*n/gg);
    return 0;
}
/*
input
5
1 2 1
1 3 2
1 4 1
2 5 3
output
13/25
*/

View Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=20005,M=40005,inf=0x3f3f3f3f;
int n,re=0,tot=0,Next[M],to[M],val[M],head[M],rt,sum,sz[N],pp[N],arr[N],tong[3],gg;
inline void add(int x,int y,int z){Next[++tot]=head[x];to[tot]=y;val[tot]=z;head[x]=tot;}
inline int gcd(int x,int y){return (y==0)?x:gcd(y,x%y);}
inline void getrt(int x,int fa)
{
    int i; sz[x]=1; pp[x]=0;
    for(i=head[x];i;i=Next[i])
    {
        if(!arr[to[i]]&&to[i]!=fa){getrt(to[i],x); sz[x]+=sz[to[i]]; pp[x]=max(pp[x],sz[to[i]]);}
    }pp[x]=max(pp[x],sum-pp[x]); if(pp[x]<pp[rt])rt=x;
}
inline void dfs(int x,int fa,int pre)
{
    tong[pre]++; int i;
    for(i=head[x];i;i=Next[i])
    {
        if(to[i]!=fa&&!arr[to[i]])dfs(to[i],x,(pre+val[i])%3);
    }
}
inline void calc(int x,int op,int v)
{
    tong[0]=tong[1]=tong[2]=0; dfs(x,0,v%3); re+=op*(2*tong[1]*tong[2]+tong[0]*tong[0]+tong[1]+tong[2]);
}
inline void solve(int x)
{
    int i; arr[x]=1; calc(x,1,0);
    for(i=head[x];i;i=Next[i])
    {
        if(!arr[to[i]])
        {
            calc(to[i],-1,val[i]); sum=sz[to[i]]; pp[rt=0]=inf; getrt(to[i],0); solve(rt);
        }
    }
}
int main()
{
    int i,x,y,z; scanf("%d",&n); sum=pp[rt=0]=n;
    for(i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);
    }getrt(1,0); solve(rt); gg=gcd(re,n*n); printf("%d/%d
",re/gg,n*n/gg);
}

点分