TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4110
  • 题目
  • P4110FJ2015省队集训day1 石子游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 165537 KB
    问题描述

    石子游戏是大家都很喜欢玩的一类游戏,这类游戏通常与石子的移动和取 舍有关,往往可以让人在游戏中获得不少的乐趣。

    有一类树上石子游戏的规则是这样的:在一棵有根树上,每个节点都有着 一定数目的石子,两个玩家轮流进行游戏。每次,每个玩家可以把不超过 m 个 的石子移动到它的父亲上。显然,根节点没有父亲,故每个石子一旦移动到根 节点便无法再次移动。问题是以某个节点为根的子树进行这样的游戏,是否存 在先手必胜策略。

    为了增加这个游戏的难度,我们对这个游戏进行一些小小的修改。现在, 我们的这棵树可能会长出新的节点。同时,每个节点上的石子数目可能会变化。 请问,以某个节点为根的子树进行这样的石子游戏,是否存在先手必胜策略。

    输入格式

    输入文件 game.in 第一行包含两个数字 n 和 m,表示初始时有 n 个节点, 每次移动不能超过 m 个。

    第二行 n 个正整数 a1, a2, . . . , an,表示初始时候的石子数量,其中 1 号节 点为根节点。

    接下来 n − 1 行,每行两个整数 u 和 v,表示有一条从 u 到 v 的边。

    接下来一行一个数 t, 表示操作的数目。

    接下来 t 行,每行代表一个操作,每行的第一个数字代表操作类型,其中:

    若为 1,后跟一个数字 v,表示询问在 v 的子树中做游戏先手是否必胜。

    若为 2,后跟两个数字 x, y 表示将节点 x 的石子数修改为 y。

    若为 3,后跟三个数字 u, v, x,表示为 u 节点添加一个儿子 v,初始石 子数为 x。

    输出格式

    输出文件 game.out 对于每一个询问,若先手必胜输出“Yes”,否则输出 “No”。

    注,数据进行了强制在线处理,对于每一个操作,除类型名外,都需要异 或之前回答为“Yes“的数目。

    样例输入

    2 1000
    0 0
    1 2
    1
    1 1

    样例输出

    No

    提示

    对于 40% 的数据,不存在修改和添加操作,其中有 10% 的数据,所有节 点都与根节点直接相连,共 4 个点,每个点 10 分。

    对于另外 60% 的数据,存在修改和添加操作,共 4 个点,每个点 15 分。

    对于 100% 的数据, n, t ≤ 50000。

    同时,保证任何时刻树中节点数目和编号都不会超过100000。其余数据的范围皆在 int 范围内。


    来源  感谢1879570236