hdu5227 Tom and game(BestCoder Round #40)

hdu5227 Tom and game(BestCoder Round #40)

Tom and game

问题描述

Tom喜欢和Tony玩游戏。他们认为一个有序四元组(t,i,j,k)是合法的，当且仅当满足：1、1≤i,j,k≤t

输入描述

输入包含多组数据（大约8组）。对于每组数据，第一行一个正整数n，表示树上有n个结点，从1开始编号。接下来n-1行，每行两个正整数i、j，表示i、j之间有一条边。接下来n行，第i行有四个正整数a、b、c、d，表示编号为i的点上的四元组是(a,b,c,d)。1≤n≤10000;1≤i,j≤n;1≤a,b,c,d≤10000

输出描述

对于每组数据，输出一行一个分数"a/b"，表示获胜概率，要求a、b互质。若必败，要输出"0/1"。

输入样例

2 1 2 1 1 1 1 2 1 2 1 5 1 2 2 3 3 4 4 5 1 1 1 1 2 1 1 1 2 1 2 1 2 2 1 1 1 1 1 1

输出样例

3/4 3/5

Problem D概率就是(必胜的点对数/总点对数)，总点对数是n2，我们需要考虑如何求必胜点对数。这个游戏就像是Nim游戏，一个四元组就相当于一堆石头，石头的数量就是字典序比它小的合法四元组的个数，同时也是这个四元组的SG值。考虑如何求字典序比(a,b,c,d)小的合法四元组(p,q,s,t)的数量：1、p

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。