本文主要是介绍BZOJ 2152 (树形DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2152: 聪聪可可
Time Limit: 3 Sec Memory Limit: 259 MBSubmit: 798 Solved: 419
[ Submit][ Status][ Discuss]
Description
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
Input
输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。
Output
以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。
Sample Input
5
1 2 1
1 3 2
1 4 1
2 5 3
1 2 1
1 3 2
1 4 1
2 5 3
Sample Output
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。
【样例说明】
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。
dp[i][j]:表示（以当前节点为根的子树中）链接到j节点路径长度的模值i（i=0,1,2，模3）的节点个数；当然 siz[j] = 1 + dp[0][j] +dp[1][j] +dp[2][j];
状态转移方程为 dp[(i+v)%3][father] = dp[i][sons];其中v为father到一个son的路径长度模3;#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 20010
struct Edge{int value,id,next;Edge(){}Edge(int _id,int v,int nxt){id = _id;value = v;next = nxt;}
}edge[2*N];
int dp[3][N];
int head[2*N];
int n,ans,a,b,e_top;
void addEdge(int x,int y,int v){edge[e_top].id = y;edge[e_top].value = v;edge[e_top].next = head[x];head[x] = e_top++;
}
int gcd(int x,int y){if(y==0) return x;return gcd(y,x%y);
}
void update(int fa,int ch,int v){if(v==0) {ans += dp[0][fa]*(dp[0][ch] + 1);ans += dp[1][fa]*dp[2][ch] + dp[2][fa]*dp[1][ch];ans += (dp[0][ch] + 1);}if(v==1) {ans += dp[0][fa]*dp[2][ch];ans += dp[1][fa]*dp[1][ch] + dp[2][fa]*(dp[0][ch]+1);ans += dp[2][ch];}if(v==2) {ans += dp[0][fa]*dp[1][ch];ans += dp[1][fa]*(dp[0][ch]+1) + dp[2][fa]*dp[2][ch];ans += dp[1][ch];}
}
void dfs(int cur,int fa){dp[0][cur] = dp[1][cur] = dp[2][cur] = 0;for(int i = head[cur];i != -1;i=edge[i].next){int next = edge[i].id;int v = edge[i].value;if(next == fa) continue;dfs(next,cur);update(cur,next,v%3);dp[v%3][cur] += 1;for(int j = 0;j<=2;j++)dp[(j+v)%3][cur] += dp[j][next];}
}
void init(){memset(head,-1,sizeof(head));e_top = ans = 0;
}
int main(){//freopen("Test.txt","r",stdin);int x,y,v;while(~scanf("%d",&n)){init();for(int i = 1;i<=n-1;i++){scanf("%d%d%d",&x,&y,&v);addEdge(x,y,v%3);addEdge(y,x,v%3);}dfs(1,-1);a = 2*ans+n; b = n*n;printf("%d/%d\n",a/gcd(a,b),b/gcd(a,b));}return 0;
}
这篇关于BZOJ 2152 (树形DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
