CF482E ELCA

有一棵以 $1$ 为根的有根树，第 $i$ 个节点的父亲为 $f_i$，每个节点上有一个数为 $a_i$。 共有 $m$ 个事件： `P x y` : 若 $x$ 是 $y$ 的祖先，把 $f_y$ 改为 $x$，否则把$ f_x$ 改为 $y$。 `V x v` : 把 $a_x$ 改为 $v$。 求初始和每个事件发生后随机两个点（可以是同一个点）的 LCA 的 $a_i$ 的期望

第一行有一个整数n 第二行有n-1个整数，第i个整数是$f_{i+1}$ 第三行有n个整数，第i个整数是$a_i$ 第四行有一个整数m 接下来m行每行有一个事件

共m+1行，输出初始和每个事件发生后随机两个点（可以是同一个点）的LCA的$a_i$的期望

You have a root tree containing $ n $ vertexes. Let's number the tree vertexes with integers from $ 1 $ to $ n $ . The tree root is in the vertex $ 1 $ . Each vertex (except fot the tree root) $ v $ has a direct ancestor $ p_{v} $ . Also each vertex $ v $ has its integer value $ s_{v} $ . Your task is to perform following queries: - P $ v $ $ u $ ( $ u≠v $ ). If $ u $ isn't in subtree of $ v $ , you must perform the assignment $ p_{v}=u $ . Otherwise you must perform assignment $ p_{u}=v $ . Note that after this query the graph continues to be a tree consisting of $ n $ vertexes. - V $ v $ $ t $ . Perform assignment $ s_{v}=t $ . Your task is following. Before starting performing queries and after each query you have to calculate expected value written on the lowest common ancestor of two equiprobably selected vertices $ i $ and $ j $ . Here lowest common ancestor of $ i $ and $ j $ is the deepest vertex that lies on the both of the path from the root to vertex $ i $ and the path from the root to vertex $ j $ . Please note that the vertices $ i $ and $ j $ can be the same (in this case their lowest common ancestor coincides with them).