CF1806E.Tree Master
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a tree with n weighted vertices labeled from 1 to n rooted at vertex 1 . The parent of vertex i is pi and the weight of vertex i is ai . For convenience, define p1=0 .
For two vertices x and y of the same depth † , define f(x,y) as follows:
- Initialize ans=0 .
- While both x and y are not 0 :
- ans←ans+ax⋅ay ;
- x←px ;
- y←py .
- f(x,y) is the value of ans .
You will process q queries. In the i -th query, you are given two integers xi and yi and you need to calculate f(xi,yi) .
† The depth of vertex v is the number of edges on the unique simple path from the root of the tree to vertex v .
输入格式
The first line contains two integers n and q ( 2≤n≤105 ; 1≤q≤105 ).
The second line contains n integers a1,a2,…,an ( 1≤ai≤105 ).
The third line contains n−1 integers p2,…,pn ( 1≤pi<i ).
Each of the next q lines contains two integers xi and yi ( 1≤xi,yi≤n ). It is guaranteed that xi and yi are of the same depth.
输出格式
Output q lines, the i -th line contains a single integer, the value of f(xi,yi) .
输入输出样例
输入#1
6 2 1 5 2 3 1 1 1 2 3 3 2 4 5 6 6
输出#1
33 27
输入#2
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
输出#2
47 53 48 36 42 36 48 14
说明/提示
Consider the first example:
In the first query, the answer is a4⋅a5+a3⋅a3+a2⋅a2+a1⋅a1=3+4+25+1=33 .
In the second query, the answer is a6⋅a6+a2⋅a2+a1⋅a1=1+25+1=27 .