{"problem":{"name":"BZOJ4202 石子游戏","description":{"content":"石子游戏是大家都很喜欢玩的一类游戏，这类游戏通常与石子的移动和取舍有关，往往可以让人在游戏中获得不少的乐趣。 有一类树上石子游戏的规则是这样的：在一棵有根树上，每个结点都有着一定数目的石子，两个玩家轮流进行游戏。每次，每个玩家可以把不超过 $m$ 个的石子移动到它的父亲上，一次只能移动一个结点上的石子。显然，根结点没有父亲，故每个石子一旦移动到根结点便无法再次移动。问题是以某个结点为根的子树进行","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10662"},"statements":[{"statement_type":"Markdown","content":"石子游戏是大家都很喜欢玩的一类游戏，这类游戏通常与石子的移动和取舍有关，往往可以让人在游戏中获得不少的乐趣。\n\n有一类树上石子游戏的规则是这样的：在一棵有根树上，每个结点都有着一定数目的石子，两个玩家轮流进行游戏。每次，每个玩家可以把不超过 $m$ 个的石子移动到它的父亲上，一次只能移动一个结点上的石子。显然，根结点没有父亲，故每个石子一旦移动到根结点便无法再次移动。问题是以某个结点为根的子树进行这样的游戏，是否存在先手必胜策略。\n\n为了增加这个游戏的难度，我们对这个游戏进行一些小小的修改。现在，我们的这棵树可能会长出新的结点。同时，每个结点上的石子数目可能会变化。请问，以某个节点为根的子树进行这样的石子游戏，是否存在先手必胜策略。本题要求强制在线。\n\n## Input\n\n第一行包含两个整数 $n,m$，表示初始时有 $n$ 个结点，每次移动不能超过 $m$ 个石子。\n\n第二行 $n$ 个正整数 $a_1,a_2,\\dots,a_n$，表示初始时候的石子数量，其中 $1$ 号结点为根结点。\n\n接下来 $n-1$ 行，每行两个整数 $u,v$，表示有一条从 $u$ 到 $v$ 的边。\n\n接下来一行一个正整数 $t$，表示操作的数目。\n\n接下来 $t$ 行，每行代表一个操作，每行的第一个数字代表操作类型，其中：\n\n- 若为 $1$，后跟一个整数 $v$，表示询问在 $v$ 的子树中做游戏先手是否必胜。\n- 若为 $2$，后跟两个整数 $x,y$，表示将结点 $x$ 的石子数修改为 $y$。\n- 若为 $3$，后跟三个整数 $u,v,x$，表示为 $u$ 结点添加一个儿子 $v$，其初始石子数为 $x$。\n\n## Output\n\n对于每一个询问，若先手必胜输出 `Yes`，否则输出 `No`。\n\n注：数据进行了强制在线处理，对于每一个操作，除类型名外，都需要异或之前回答为 `Yes` 的数目。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，$1\\leq n,t\\leq 5\\times 10^4$，同时，保证任何时刻树中节点数目和编号都不会超过 $10^5$。其余数据的范围皆在 int 范围内。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10662","tags":["O2优化","动态树 LCT","分块"],"sample_group":[["2 1000\n0 0\n1 2\n1\n1 1","No"]],"created_at":"2026-03-03 11:09:25"}}