{"problem":{"name":"[Ynoi Easy Round 2022] 虚空处刑 TEST_105","description":{"content":"给定一棵 $n$ 个节点的树，第 $i$ 个点有点权 $a_i$。 定义一个点 $x$ 所在的极大同色连通块为一个**极大的**点集 $S$，满足 $x\\in S$，且对任意点集中的元素 $i,j$，可以找到一个节点序列 $p_1,p_2,...p_t$，满足 $p_1=i$，$p_t=j$，且对任意 $k$ 为 $[1,t)$ 中的整数，满足 $p_k$ 与 $p_{k+1}$ 在树上相邻，且","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9067"},"statements":[{"statement_type":"Markdown","content":"给定一棵 $n$ 个节点的树，第 $i$ 个点有点权 $a_i$。\n\n定义一个点 $x$ 所在的极大同色连通块为一个**极大的**点集 $S$，满足 $x\\in S$，且对任意点集中的元素 $i,j$，可以找到一个节点序列 $p_1,p_2,...p_t$，满足 $p_1=i$，$p_t=j$，且对任意 $k$ 为 $[1,t)$ 中的整数，满足 $p_k$ 与 $p_{k+1}$ 在树上相邻，且 $a_{p_k}=a_{p_{k+1}}$，且 $p_k\\in S$。\n\n有 $m$ 次操作：\n\n`1 x y`：给出一个点 $x$ ，将其所在的极大同色连通块中每个点的点权修改为 $y$。\n\n`2 x`：给出一个点 $x$，查询其所在的极大同色连通块的大小。\n\n## Input\n\n第一行两个数 $n,m$。\n\n第二行 $n-1$ 个数，第 $i$ 个数表示树上第 $i+1$ 的节点的父亲节点的编号，保证父亲节点的编号比该节点小。\n\n第三行 $n$ 个数，第 $i$ 个数表示 $a_i$。\n\n之后 $m$ 行，每行形如 `1 x y` 或 `2 x`，意义如上述。\n\n## Output\n\n对每个 $2$ 操作，输出一行一个数表示答案。\n\n[samples]\n\n## Background\n\n我要对不死者先生你施展魔法，希望你能看到，更多美好的事物，希望你能见识到，更多我无法见识的事物，希望...你的心...不管几次都能苏——\n\n......\n\n你的魔法为时已晚了，和知道没有办法可以救你是一样的，仿佛就像是这什么都没有的天空一样啊——\n\n星星？\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/1q0z7j3z.png)\n\n......\n\n星星呢？有个星形的星星飘在天上？\n\n像那种奇妙的东西啊，是超人机械的产物哦。\n\n......\n\n已不能，继续光顾着追求星星...\n\n不死者的本体的确不见得是在那颗星星上，我也知道他们大多是脱离常轨的危险任务，这些我都明白...\n\n但天上就是飘着那种星星啊，超人机械或许就在上面，史前的睿智肯定堆积如山。\n\n......\n\n星形的理由是个迷，也看不出任何工学上的必然性。但他若是以自然物为基础打造的，那这形状就说得通了。\n\n正确来说，我认为那是个群体，而不是单一生命体，且若它是生物，那就可预想它有着机械所没有的优点，像是自然修复损毁部位，透过增殖解决经年老化问题，甚至可能是以不需管理者为前提所打造的。\n\n目前我们还不理解它是用什么系统来维持飞行轨道，但高度应该是最佳环境不会错。\n\n连次元的墙壁都能跨越的超绝知性体，怎么可能将与自身相关的重要机构，放在区区三万六千公里高的天空上？\n\n你不觉得魔法是个很极端的东西吗？光用想的就能产生出热或质量，这实在太荒唐了，超越人智，犹如神般的存在姑且先不谈，一个小小的生命，人类的亚种，魔法使们怎么可能会有如此强大的力量？\n\n魔法使换句话说就是水龙头，水源则是另在别处。\n\n星星是超人机械所撒下的，供应魔力与抑制魔法的生命机器，除此以外可能什么都不是吧。\n\n......\n\n我们已经不做星星的梦了。\n\n魔法产生的原理，一旦被世人知道，就会引发末日战争。现在我们只能尽全力透过操控情报，让世人不对此事感兴趣。\n\n## Note\n\nIdea：nzhtl1477，Solution：nzhtl1477，Code：ccz181078，Data：ccz181078\n\n对于 $20\\%$ 的数据，满足 $n,m\\leq2\\times 10^3$。\n\n对于 $40\\%$ 的数据，满足 $n,m\\leq2\\times 10^5$。\n\n对于另外 $30\\%$ 的数据，满足 $1\\le a_i,y\\le 2$。\n\n对于 $100\\%$ 的数据，满足 $1\\le n,m,a_i,x,y\\le10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9067","tags":["2022","O2优化","Ynoi"],"sample_group":[["4 5\n1 1 2\n3 1 1 1\n2 4\n1 1 1\n1 4 3\n2 4\n1 3 3","2\n4"]],"created_at":"2026-03-03 11:09:25"}}