这题 CF *3100，应该评黑（翻译过分简化期望式子了）。可能大佬都把动态开点线段树当成暴力来写吧

坑点（我跳的）：

• 当不存在该颜色时，答案为 $c\times c$，而不是 $0$。

• 好像不太好维护区间内有效（存在）值的个数，因此无法标记永久化（wtcl）。

• pushdown 时，儿子平方项加上的常数项是 $\text{tag}^2$ 而不是 $\text{tag}$。

翻译（形式化，源码点击链接或看二楼）：

• 给出一棵 $n$ 个节点的有根树，根为 $1$。点 $2\sim n$ 的父亲为 $p_2\sim p_n$。有 $m$ 种颜色。点 $i$ 的颜色为 $f_i$，颜色 $i$ 的权值为 $c_i$。有两种操作共 $q$ 次：

  • $\texttt{1 }x\text{ }y$，将 $c_x\leftarrow y$。

  • $\texttt{2 }x$，从树中等概率选取一个点 $i$，得到 $(S_i\times b_x-C)^2$ 的价值。求期望价值。其中 $S_i$ 表示以 $i$ 为根的子树中颜色为 $x$ 的节点数。$C$ 是给定的常数。

输入格式

• 第一行四个自然数 $n,m,q,C(2\le n\le 5\times 10^4,1\le m,q\le 5\times 10^4,0\le C\le 10^6)$。

• 第二行 $n$ 个正整数 $f_1\sim f_n(1\le f_i\le m)$。

• 第三行 $n-1$ 个正整数为 $p_2\sim p_n(1\le p_i\le n)$。

• 第四行 $m$ 个正整数 $c_1\sim c_m(1\le c_i\le 100)$。

• 第 $5\sim n+3$ 行每行两个正整数 $u,v$，为树边。

• 第 $n+3\sim n+q+2$ 行每行为一个操作 $\texttt{1 }x\text{ }y$ 或 $\texttt{2 }x$。

输出格式

对于 $\texttt{2}$ 操作，输出期望。

tag：线段树，树链剖分，期望