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).

输入输出格式

输入格式

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).

输出格式

Print $ q+1 $ number — the corresponding expected values. Your answer will be considered correct if its absolute or relative error doesn't exceed $ 10^{-9} $ .

输入输出样例

输入样例 #1

5
1 2 2 1
1 2 3 4 5
5
P 3 4
P 4 5
V 2 3
P 5 2
P 1 4

输出样例 #1

1.640000000
1.800000000
2.280000000
2.320000000
2.800000000
1.840000000

说明

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).

题意翻译

### 题目描述 有一棵以 $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$的期望