Tree Master (Codeforces 1806E)
Tags: Others, trees

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

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

Sample Inputs:
6 2
1 5 2 3 1 1
1 2 3 3 2
4 5
6 6

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

Sample Outputs:
33
27

47
53
48
36
42
36
48
14

Solution (Python):
import sys
import math
import heapq
import bisect
from collections import Counter, defaultdict, deque
from io import BytesIO, IOBase
from types import GeneratorType
import string
from itertools import combinations

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
    return int(input())

def get_ints():
    return list(map(int, input().split(' ')))

def get_int_grid(n):
    return [get_ints() for _ in range(n)]

def get_str():
    return input().strip()

def get_strs():
    return get_str().split(' ')

def yes_no(b):
    if b:
        return 'YES'
    else:
        return 'NO'

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def binary_search(good, left, right, delta=1, right_true=False):
    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False

def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p

def solve_a():
    (a, b, c, d) = get_ints()
    cnt = 0
    if d < b:
        return -1
    else:
        moves = d - b
        cnt += moves
        b += moves
        a += moves
    if a < c:
        return -1
    else:
        moves = a - c
        cnt += moves
    return cnt

def solve_b():
    n = get_int()
    a = get_ints()
    (z, o) = (a.count(0), a.count(1))
    if z < n + 3 >> 1:
        return 0
    elif o >= 1 and z + o == n:
        return 2
    else:
        return 1

def solve_c():
    n = get_int()
    a = get_ints()
    toz = 0
    if n == 1:
        return max(a) - min(a)
    L = 0
    R = 1
    while pow(R, n - 1) < n:
        R *= 2
    while R - L > 1:
        z = L + R >> 1
        if pow(z, n - 1) >= n:
            R = z
        else:
            L = z
    best = float('inf')
    for x in a:
        toz += abs(x)
    best = min(best, toz)
    toR = 0
    if pow(R, n - 1) == n:
        for x in a:
            toR += abs(R - x)
        best = min(best, toR)
    if n % 2 == 0:
        tomix = 0
        a.sort()
        tomix += abs(n - a.pop())
        while a:
            tomix += abs(-1 - a.pop())
        best = min(best, tomix)
    return best

def solve_e():
    (n, q) = get_ints()
    a = get_ints()
    p = [-1] + [x - 1 for x in get_ints()]
    G = [[] for _ in range(n)]
    for i in range(1, n):
        G[i].append(p[i])
        G[p[i]].append(i)
    d = [0] * n
    f_xx = [0] * n

    @bootstrap
    def dfs1(u, p):
        f_xx[u] = f_xx[p] + a[u] * a[u]
        for v in G[u]:
            if v == p:
                continue
            d[v] = d[u] + 1
            yield dfs1(v, u)
        yield
    dfs1(0, -1)
    fvals = defaultdict(int)

    def f(u, v):
        if (u, v) in fvals:
            return fvals[u, v]
        (u_tmp, v_tmp) = (u, v)
        res = 0
        while u_tmp != v_tmp and d[u_tmp] & (1 << 6) - 1:
            res += a[u_tmp] * a[v_tmp]
            (u_tmp, v_tmp) = (p[u_tmp], p[v_tmp])
        if u_tmp == v_tmp:
            fvals[u, v] = res + f_xx[u_tmp]
            fvals[v, u] = fvals[u, v]
            return fvals[u, v]
        else:
            fvals[u, v] = res + f(p[u_tmp], p[v_tmp]) + a[u_tmp] * a[v_tmp]
            fvals[v, u] = fvals[u, v]
            return fvals[u, v]
    ans = []
    for _ in range(q):
        (u, v) = get_ints()
        u -= 1
        v -= 1
        ans.append(f(u, v))
    return ans
print(*solve_e())

Solution (Python):
import sys
import math
import heapq
import bisect
from collections import Counter, defaultdict, deque
from io import BytesIO, IOBase
from types import GeneratorType
import string
from itertools import combinations

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
    return int(input())

def get_ints():
    return list(map(int, input().split(' ')))

def get_int_grid(n):
    return [get_ints() for _ in range(n)]

def get_str():
    return input().strip()

def get_strs():
    return get_str().split(' ')

def yes_no(b):
    if b:
        return 'YES'
    else:
        return 'NO'

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def binary_search(good, left, right, delta=1, right_true=False):
    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False

def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p

def solve_a():
    (a, b, c, d) = get_ints()
    cnt = 0
    if d < b:
        return -1
    else:
        moves = d - b
        cnt += moves
        b += moves
        a += moves
    if a < c:
        return -1
    else:
        moves = a - c
        cnt += moves
    return cnt

def solve_b():
    n = get_int()
    a = get_ints()
    (z, o) = (a.count(0), a.count(1))
    if z < n + 3 >> 1:
        return 0
    elif o >= 1 and z + o == n:
        return 2
    else:
        return 1

def solve_c():
    n = get_int()
    a = get_ints()
    toz = 0
    if n == 1:
        return max(a) - min(a)
    L = 0
    R = 1
    while pow(R, n - 1) < n:
        R *= 2
    while R - L > 1:
        z = L + R >> 1
        if pow(z, n - 1) >= n:
            R = z
        else:
            L = z
    best = float('inf')
    for x in a:
        toz += abs(x)
    best = min(best, toz)
    toR = 0
    if pow(R, n - 1) == n:
        for x in a:
            toR += abs(R - x)
        best = min(best, toR)
    if n % 2 == 0:
        tomix = 0
        a.sort()
        tomix += abs(n - a.pop())
        while a:
            tomix += abs(-1 - a.pop())
        best = min(best, tomix)
    return best

def solve_e():
    (n, q) = get_ints()
    a = get_ints()
    p = [-1] + [x - 1 for x in get_ints()]
    d = [0] * n
    f_xx = [0] * n
    for (i, par) in enumerate(p):
        f_xx[i] += a[i] * a[i]
        if i:
            d[i] = d[par] + 1
            f_xx[i] += f_xx[par]
    fvals = defaultdict(int)

    def f(u, v):
        if u > v:
            (u, v) = (v, u)
        if u + n * v in fvals:
            return fvals[u + n * v]
        (u_tmp, v_tmp) = (u, v)
        res = 0
        while u_tmp != v_tmp and d[u_tmp] & (1 << 7) - 1:
            res += a[u_tmp] * a[v_tmp]
            (u_tmp, v_tmp) = (p[u_tmp], p[v_tmp])
        if u_tmp == v_tmp:
            fvals[u + n * v] = res + f_xx[u_tmp]
            return fvals[u + n * v]
        else:
            fvals[u + n * v] = res + f(p[u_tmp], p[v_tmp]) + a[u_tmp] * a[v_tmp]
            return fvals[u + n * v]
    ans = []
    for _ in range(q):
        (u, v) = get_ints()
        u -= 1
        v -= 1
        ans.append(f(u, v))
    return ans
print(*solve_e())

Solution (Python):
import sys
import math
import heapq
import bisect
from collections import Counter, defaultdict, deque
from io import BytesIO, IOBase
from types import GeneratorType
import string
from itertools import combinations

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
    return int(input())

def get_ints():
    return list(map(int, input().split(' ')))

def get_int_grid(n):
    return [get_ints() for _ in range(n)]

def get_str():
    return input().strip()

def get_strs():
    return get_str().split(' ')

def yes_no(b):
    if b:
        return 'YES'
    else:
        return 'NO'

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def binary_search(good, left, right, delta=1, right_true=False):
    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False

def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p

def solve_a():
    (a, b, c, d) = get_ints()
    cnt = 0
    if d < b:
        return -1
    else:
        moves = d - b
        cnt += moves
        b += moves
        a += moves
    if a < c:
        return -1
    else:
        moves = a - c
        cnt += moves
    return cnt

def solve_b():
    n = get_int()
    a = get_ints()
    (z, o) = (a.count(0), a.count(1))
    if z < n + 3 >> 1:
        return 0
    elif o >= 1 and z + o == n:
        return 2
    else:
        return 1

def solve_c():
    n = get_int()
    a = get_ints()
    toz = 0
    if n == 1:
        return max(a) - min(a)
    L = 0
    R = 1
    while pow(R, n - 1) < n:
        R *= 2
    while R - L > 1:
        z = L + R >> 1
        if pow(z, n - 1) >= n:
            R = z
        else:
            L = z
    best = float('inf')
    for x in a:
        toz += abs(x)
    best = min(best, toz)
    toR = 0
    if pow(R, n - 1) == n:
        for x in a:
            toR += abs(R - x)
        best = min(best, toR)
    if n % 2 == 0:
        tomix = 0
        a.sort()
        tomix += abs(n - a.pop())
        while a:
            tomix += abs(-1 - a.pop())
        best = min(best, tomix)
    return best

def solve_e():
    (n, q) = get_ints()
    a = get_ints()
    p = [-1] + [x - 1 for x in get_ints()]
    G = [[] for _ in range(n)]
    for i in range(1, n):
        G[i].append(p[i])
        G[p[i]].append(i)
    d = [0] * n
    f_xx = [0] * n

    @bootstrap
    def dfs1(u, p):
        f_xx[u] = f_xx[p] + a[u] * a[u]
        for v in G[u]:
            if v == p:
                continue
            d[v] = d[u] + 1
            yield dfs1(v, u)
        yield
    dfs1(0, -1)
    fvals = defaultdict(int)

    def f(u, v):
        if u > v:
            (u, v) = (v, u)
        if u + n * v in fvals:
            return fvals[u + n * v]
        (u_tmp, v_tmp) = (u, v)
        res = 0
        while u_tmp != v_tmp and d[u_tmp] & (1 << 7) - 1:
            res += a[u_tmp] * a[v_tmp]
            (u_tmp, v_tmp) = (p[u_tmp], p[v_tmp])
        if u_tmp == v_tmp:
            fvals[u + n * v] = res + f_xx[u_tmp]
            return fvals[u + n * v]
        else:
            fvals[u + n * v] = res + f(p[u_tmp], p[v_tmp]) + a[u_tmp] * a[v_tmp]
            return fvals[u + n * v]
    ans = []
    for _ in range(q):
        (u, v) = get_ints()
        u -= 1
        v -= 1
        ans.append(f(u, v))
    return ans
print(*solve_e())