CF482E ELCA

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} $ .

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