310261: CF1806E. Tree Master

Memory Limit:1024 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Tree Mastertime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given a tree with $n$ weighted vertices labeled from $1$ to $n$ rooted at vertex $1$. The parent of vertex $i$ is $p_i$ and the weight of vertex $i$ is $a_i$. For convenience, define $p_1=0$.

For two vertices $x$ and $y$ of the same depth$^\dagger$, define $f(x,y)$ as follows:

  • Initialize $\mathrm{ans}=0$.
  • While both $x$ and $y$ are not $0$:
    • $\mathrm{ans}\leftarrow \mathrm{ans}+a_x\cdot a_y$;
    • $x\leftarrow p_x$;
    • $y\leftarrow p_y$.
  • $f(x,y)$ is the value of $\mathrm{ans}$.

You will process $q$ queries. In the $i$-th query, you are given two integers $x_i$ and $y_i$ and you need to calculate $f(x_i,y_i)$.

$^\dagger$ The depth of vertex $v$ is the number of edges on the unique simple path from the root of the tree to vertex $v$.

Input

The first line contains two integers $n$ and $q$ ($2 \le n \le 10^5$; $1 \le q \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$).

The third line contains $n-1$ integers $p_2, \ldots, p_n$ ($1 \le p_i < i$).

Each of the next $q$ lines contains two integers $x_i$ and $y_i$ ($1\le x_i,y_i\le n$). It is guaranteed that $x_i$ and $y_i$ are of the same depth.

Output

Output $q$ lines, the $i$-th line contains a single integer, the value of $f(x_i,y_i)$.

ExamplesInput
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6
Output
33
27
Input
14 8
3 2 5 3 1 4 2 2 2 5 5 5 2 4
1 2 3 1 1 4 7 3 3 1 5 3 8
4 4
4 10
13 10
3 12
13 9
3 12
9 10
11 5
Output
47
53
48
36
42
36
48
14
Note

Consider the first example:

In the first query, the answer is $a_4\cdot a_5+a_3\cdot a_3+a_2\cdot a_2+a_1\cdot a_1=3+4+25+1=33$.

In the second query, the answer is $a_6\cdot a_6+a_2\cdot a_2+a_1\cdot a_1=1+25+1=27$.

Input

题意翻译

给定一个 $n$ 个节点的树,每个节点都有权值 $a_i$。对于第 $i(1<i\le n)$ 个节点,有父亲节点 $p_i$(规定 $p_1=0$)。现有两个相同深度的节点 $x,y$,规定 $f(x,y)=\begin{cases}0&(x=y=0)\\f(p_x,p_y)+a_x\cdot a_y&(x,y\neq0)\end{cases}$,求 $f(x,y)$。 Translated by @[_JYqwq_](/user/400269)

Output

题目大意:
给定一个带权重的树,树的节点数为n,节点编号从1到n,以节点1为根。每个节点的父节点为p_i,节点的权重为a_i。为了方便,定义p_1=0。对于树中同一深度的任意两个节点x和y,定义函数f(x,y)如下:
1. 初始化ans=0。
2. 当x和y都不为0时,执行以下操作:
- ans←ans+a_x⋅a_y;
- x←p_x;
- y←p_y。
3. f(x,y)的值为ans。

你需要处理q个查询。在第i个查询中,你会得到两个整数x_i和y_i,需要计算f(x_i,y_i)。

输入输出数据格式:
输入:
- 第一行包含两个整数n和q(2≤n≤10^5;1≤q≤10^5)。
- 第二行包含n个整数a_1,a_2,…,a_n(1≤a_i≤10^5)。
- 第三行包含n-1个整数p_2,…,p_n(1≤p_i - 接下来的q行,每行包含两个整数x_i和y_i(1≤x_i,y_i≤n)。保证x_i和y_i是同一深度的节点。

输出:
- q行,第i行包含一个整数,表示f(x_i,y_i)的值。

示例输入输出:
输入:
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6

输出:
33
27

输入:
14 8
3 2 5 3 1 4 2 2 2 5 5 5 2 4
1 2 3 1 1 4 7 3 3 1 5 3 8
4 4
4 10
13 10
3 12
13 9
3 12
9 10
11 5

输出:
47
53
48
36
42
36
48
14题目大意: 给定一个带权重的树,树的节点数为n,节点编号从1到n,以节点1为根。每个节点的父节点为p_i,节点的权重为a_i。为了方便,定义p_1=0。对于树中同一深度的任意两个节点x和y,定义函数f(x,y)如下: 1. 初始化ans=0。 2. 当x和y都不为0时,执行以下操作: - ans←ans+a_x⋅a_y; - x←p_x; - y←p_y。 3. f(x,y)的值为ans。 你需要处理q个查询。在第i个查询中,你会得到两个整数x_i和y_i,需要计算f(x_i,y_i)。 输入输出数据格式: 输入: - 第一行包含两个整数n和q(2≤n≤10^5;1≤q≤10^5)。 - 第二行包含n个整数a_1,a_2,…,a_n(1≤a_i≤10^5)。 - 第三行包含n-1个整数p_2,…,p_n(1≤p_i

加入题单

上一题 下一题 算法标签: