#P4202. 石子游戏
石子游戏
石子游戏
题目描述
一棵树最初以结点 为根,每个结点上有一些石子。给定正整数 ,一次游戏只使用以指定结点 为根的子树。两人轮流从任意一个非根结点取 至 颗石子(不能超过该结点现有的数量),把它们全部移到该结点的父结点。一次只能选一个结点取石子;移到子树根的石子不能再移动。无合法操作的一方失败。
树的状态会在询问之间变化。询问只判断胜负,游戏中的假想移动不修改实际树上的石子数。
输入格式
第一行两个整数 ,分别为初始树的结点数和每次移动的上限。第二行 个非负整数 ,表示各结点初始石子数。
接下来 行,每行两个整数 ,表示一条树边。之后一行一个整数 ,接下来 行,每行一项操作:
1 v:询问在 的子树中先手是否必胜。2 x y:将结点 上的石子数改为 。3 u v x:为结点 新增一个孩子 ,其初始石子数为 。
每项操作中,除第一个数(操作类型)外,其余参数都要分别与此前输出 Yes 的次数按位异或后使用。第一次操作前该次数为 。
输出格式
每次询问输出一行。若先手必胜,输出 Yes;否则输出 No。
数据规模与约定
。任何时刻树中结点数及结点编号均不超过 。其余数值均在有符号 位整数表示范围内。
样例 #1
样例输入 #1
2 1000
0 0
1 2
1
1 1
样例输出 #1
No