题目描述

经过推选，黎瑟莫名其妙的当上了计算机系的网管。上任后的黎瑟才发现，这里的网络经常断掉。给定一棵边权均为 $1$ 的无根树，点可能是黑色或白色，支持两种操作：

• 1 x p 表示目前点 $x$ 的颜色可能发生了翻转(黑变白，白变黑)，发生概率为 $p\%$；

• 2 s 表示求 $E((\sum\limits_{x\in B}dist(x,s))^2)$，其中 $B$ 为当前黑点的集合，$dist(x,y)$ 表示 $x$ 号节点和 $y$ 号节点在树上的最短距离。

输入格式

第一行三个整数 $id,n,m$，表示数据编号，树的点数和操作个数。
第二行 $n$ 个整数 $c_i$，若 $c_i=1$ 表示点 $i$ 为黑色，否则表示点 $i$ 为白色。
接下来的 $n-1$ 行，每行两个整数 $u_i,v_i$，表示树上有一条 $u_i$ 节点到 $v_i$ 节点的边。
接下来的 $m$ 行，每行表示一个操作，格式如题。

输出格式

对于每个询问输出一行一个浮点数表示答案，输出与答案绝对误差不超过 $10^{-6}$ 就算正确。

样例输入

由于样例输入过长，请在 https://paste.ubuntu.com/p/WDTXsD6zMX/ 查看。

样例输出

由于样例输出过长，请在 https://paste.ubuntu.com/p/WDTXsD6zMX/ 查看。

数据规模与约定

对于 $100\%$ 的数据，$1 \le id \le 20$，$1 \le n \le Nid$，$0 \le m \le Nid$，$1 \le u_i, v_i, x_i, s_i \le n$，$0 \le c_i \le 1$，$0 \le p_i \le 100$。