BZOJ2152: 聪聪可可(点分治)
2018-07-12 07:32:44来源:博客园 阅读 ()
Submit: 4902 Solved: 2572
[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
1 2 1
1 3 2
1 4 1
2 5 3
Sample Output
【样例说明】
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。
HINT
Source
点分治的模板题
我们只需要统计出每个点在$\pmod 3$意义下的距离即可
每个点的答案为$sum[1] * sum[2] * 2 + sum[0] * sum[3]$
最后总的答案和$n^2$取个gcd就行
#include<cstdio> #include<vector> #include<algorithm> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) using namespace std; const int MAXN = 20001, INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } vector<Pair> v[MAXN]; int N; int siz[MAXN], maxsiz[MAXN], vis[MAXN], root, Sum, Mx, ans, dis[MAXN]; void FindRoot(int x, int fa) { siz[x] = 1; maxsiz[x] = 0; for(int i = 0; i < v[x].size(); i++) { int to = v[x][i].first, w = v[x][i].second; if(to == fa || vis[to]) continue; FindRoot(to, x); siz[x] += siz[to]; if(siz[to] > maxsiz[x]) maxsiz[x] = siz[to]; } maxsiz[x] = max(maxsiz[x], Sum - siz[x]); if(maxsiz[x] < Mx) Mx = maxsiz[x], root = x; } void GetRoot(int num, int x) { Sum = num; Mx = INF; root = 0; FindRoot(x, 0); } int num = 0; void GetDis(int x, int fa, int cur) { dis[++num] = cur % 3; for(int i = 0; i < v[x].size(); i++) { int to = v[x][i].first, w = v[x][i].second; if(to == fa || vis[to]) continue; GetDis(to, x, (cur + w) % 3); } } int calc(int x, int len) { num = 0; GetDis(x, 0, len); int sum[3] = {}; for(int i = 1; i <= num; i++) sum[dis[i] % 3]++; return sum[1] * sum[2] * 2 + sum[0] * sum[0]; } void Solve(int x) { vis[x] = 1; ans += calc(x, 0); for(int i = 0; i < v[x].size(); i++) { int to = v[x][i].first, w = v[x][i].second; if(vis[to]) continue; ans -= calc(to, w); GetRoot(siz[to], to); Solve(root); } } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif N = read(); for(int i = 1; i <= N - 1; i++) { int x = read(), y = read(), z = read(); v[x].push_back(MP(y, z)); v[y].push_back(MP(x, z)); } GetRoot(N, 1); Solve(root); int gcd = __gcd(ans, N * N); printf("%d/%d", ans / gcd, N * N / gcd); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:波兰表达式
- P2023 [AHOI2009]维护序列 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash