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