#P4202. 石子游戏

    ID: 3417 传统题 1000ms 128MiB 尝试: 62 已通过: 21 难度: 8 上传者: 标签>难度分类提高+/省选-博弈论必胜/必败状态递推构造与建模奇偶分组树算法欧拉序子树转区间数据结构FHQ Treap 分裂合并维护顺序统计量CF2500

石子游戏

石子游戏

题目描述

一棵树最初以结点 11 为根,每个结点上有一些石子。给定正整数 mm,一次游戏只使用以指定结点 vv 为根的子树。两人轮流从任意一个非根结点取 11 至 mm 颗石子(不能超过该结点现有的数量),把它们全部移到该结点的父结点。一次只能选一个结点取石子;移到子树根的石子不能再移动。无合法操作的一方失败。

树的状态会在询问之间变化。询问只判断胜负,游戏中的假想移动不修改实际树上的石子数。

输入格式

第一行两个整数 n,mn,m,分别为初始树的结点数和每次移动的上限。第二行 nn 个非负整数 aia_i,表示各结点初始石子数。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示一条树边。之后一行一个整数 tt,接下来 tt 行,每行一项操作:

  • 1 v:询问在 vv 的子树中先手是否必胜。
  • 2 x y:将结点 xx 上的石子数改为 yy。
  • 3 u v x:为结点 uu 新增一个孩子 vv,其初始石子数为 xx。

每项操作中,除第一个数(操作类型)外,其余参数都要分别与此前输出 Yes 的次数按位异或后使用。第一次操作前该次数为 00。

输出格式

每次询问输出一行。若先手必胜,输出 Yes;否则输出 No。

数据规模与约定

1≤n,t≤5×1041\le n,t\le5\times10^4。任何时刻树中结点数及结点编号均不超过 10510^5。其余数值均在有符号 3232 位整数表示范围内。

样例 #1

样例输入 #1

2 1000
0 0
1 2
1
1 1

样例输出 #1

No