Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a rooted tree with $N$ nodes (numbered $1$ through $N$; node $1$ is the root). For each $i$ ($1 ≤ i ≤ N-1$), the parent of the node $i+1$ is $p_{i}$.

You need to answer $Q$ queries. (Sounds quite familiar!) For each query, first, $W$ tasks are given to node $V$. These tasks are processed in the tree in the following way:
When a node receives $a$ tasks and it has no children, all $a$ tasks are executed by this node.
Otherwise, i.e. if the node has $K > 0$ children, where $K$ is a divisor of $a$, then this node gives $a/K$ of these tasks to each of its children. This process is performed recursively by each child on the tasks it receives.
Otherwise, i.e. if the node has $K > 0$ children, but $K$ is not a divisor of $a$, all $a$ tasks are ignored and none of this node's children receive any tasks.

For each query, find the number of tasks that are not executed, i.e. end up ignored, possibly after passing down the tree.

------  Input ------
The first line of the input contains a single integer $N$.
The second line contains $N-1$ space-separated integers $p_{1}, p_{2}, \ldots, p_{N-1}$.
The third line contains a single integer $Q$.
$Q$ lines follow. Each of these lines contains two space-separated integers $V$ and $W$ describing a query.

------  Output ------
For each query, print a single line containing one integer ― the number of tasks that are not executed.

------  Constraints ------
$1 ≤ N, Q ≤ 10^{5}$
$1 ≤ p_{i} ≤ N$ for each valid $i$
the graph described on the input is a tree
$1 ≤ V ≤ N$
$1 ≤ W ≤ 10^{6}$

------  Subtasks ------
Subtask #1 (20 points): $N ≤ 100$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
5

1 1 2 2

2

1 10

1 20
----- Sample Output 1 ------ 
5

0

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Number theory

Tree algorithms

Mathematics

Data structures


Solutions:
import sys
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
sys.setrecursionlimit(10 ** 6)
d = {}

def lcm(a, b):
	return a * b // gcd(a, b)

def took(v, w):
	ans = 0
	if w % f[v] == 0:
		return 0
	if d.get(str(v) + 's' + str(w)):
		return d[str(v) + 's' + str(w)]
	if len(g[v]) == 0:
		d[str(v) + 's' + str(w)] = 0
		return 0
	if w % len(g[v]) == 0:
		x = 0
		fact = w // len(g[v])
		for i in g[v]:
			x += took(i, fact)
		d[str(v) + 's' + str(w)] = x
		return x
	d[str(v) + 's' + str(w)] = w
	return w

def dfs(r):
	z = len(g[r])
	if z == 0:
		return 1
	y = 1
	for i in g[r]:
		x = dfs(i)
		f[i] = x
		y = lcm(x, y)
	return y * z

def compress(r):
	a = len(g[r])
	if a == 0:
		return []
	b = []
	for i in g[r]:
		b = compress(i)
	if a > 1:
		return []
	elif b == []:
		return [g[r][0]]
	else:
		g[r][0] = b[0]
		return b
n = int(input_())
a = list(map(int, input_().split()))
g = [[] for i in range(n + 1)]
f = [1 for i in range(n + 1)]
for i in range(n - 1):
	g[a[i]].append(i + 2)
f[1] = dfs(1)
compress(1)
for _ in range(int(input_())):
	(v, w) = list(map(int, input_().split()))
	print(took(v, w))


import sys
import math
sys.setrecursionlimit(10 ** 5)
input = lambda : sys.stdin.readline().strip('\r\n')
sa = lambda : input()
sb = lambda : int(input())
sc = lambda : input().split()
sd = lambda : list(map(int, input().split()))
se = lambda : float(input())
sf = lambda : list(input())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
memorise = dict()

def path_manager(graph, root):
	if len(graph[root]) < 1:
		return list()
	for child in graph[root]:
		neg = path_manager(graph, child)
	if len(graph[root]) == 1:
		if len(neg) == 0:
			return graph[root]
		else:
			graph[root][0] = neg[0]
			return neg
	else:
		return list()

def local_lcm(graph, local, root):
	if len(graph[root]) == 0:
		return 1
	temp = 1
	for child in graph[root]:
		temp1 = local_lcm(graph, local, child)
		local[child] = temp1
		temp = temp * temp1 // math.gcd(temp, temp1)
	return len(graph[root]) * temp

def query(graph, local, root, weight):
	if weight % local[root] == 0 or len(graph[root]) == 0:
		memorise[str(weight) + 'satyam' + str(root)] = 0
		return 0
	if memorise.get(str(weight) + 'satyam' + str(root)) is not None:
		return memorise[str(weight) + 'satyam' + str(root)]
	if weight % len(graph[root]) == 0:
		temp = 0
		for child in graph[root]:
			temp = temp + query(graph, local, child, weight // len(graph[root]))
		memorise[str(weight) + 'satyam' + str(root)] = temp
		return temp
	memorise[str(weight) + 'satyam' + str(root)] = weight
	return weight

def hnbhai():
	n = sb()
	parent = sd()
	graph = [list() for _ in range(n + 1)]
	local = [1] * (n + 1)
	for par in range(n - 1):
		graph[parent[par]].append(par + 2)
	local[1] = local_lcm(graph, local, 1)
	path_manager(graph, 1)
	for i in range(sb()):
		(a, b) = sd()
		print(query(graph, local, a, b))
for _ in range(1):
	hnbhai()


import sys
input_ = lambda : sys.stdin.readline().strip('\r\n')
iip = lambda : int(input_())
ilp = lambda : list(map(int, input_().split()))
pri = lambda x: print(x)
sys.setrecursionlimit(10 ** 6)

def make_tree():
	for i in range(n - 1):
		adjacency_list[a[i]].append(i + 2)

def lcm(num1, num2):
	if num1 > num2:
		num = num1
		den = num2
	else:
		num = num2
		den = num1
	rem = num % den
	while rem != 0:
		num = den
		den = rem
		rem = num % den
	gcd = den
	lcm = int(int(num1 * num2) / int(gcd))
	return lcm

def zero_ans(node):
	l = len(adjacency_list[node])
	if l == 0:
		return 1
	temp = 1
	for i in adjacency_list[node]:
		z = zero_ans(i)
		equal_distri[i] = z
		temp = lcm(temp, z)
	return l * temp

def decrease(node):
	l = len(adjacency_list[node])
	if l == 0:
		return -1
	y = -1
	for i in adjacency_list[node]:
		y = decrease(i)
	if l > 1:
		return -1
	elif y == -1:
		return adjacency_list[node][0]
	else:
		adjacency_list[node][0] = y
		return y

def find(node, total):
	l = len(adjacency_list[node])
	if total % equal_distri[node] == 0:
		return 0
	x = str(node) + '?' + str(total)
	if memo.get(x):
		return memo[x]
	if l == 0:
		memo[x] = 0
		return 0
	if total % l == 0:
		ans = 0
		dis = total // l
		for i in adjacency_list[node]:
			ans += find(i, dis)
		memo[x] = ans
		return ans
	memo[x] = total
	return total
n = iip()
a = ilp()
q = iip()
adjacency_list = [[] for i in range(n + 1)]
equal_distri = [1 for i in range(n + 1)]
memo = {}
make_tree()
equal_distri[1] = zero_ans(1)
decrease(1)
for _ in range(q):
	(node, total) = ilp()
	print(find(node, total))


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
arr = [[] for x in range(n + 1)]
temp = list(map(int, input().split()))
tog = 0
for i in range(2, n + 1):
	arr[temp[tog]].append(i)
	tog += 1
we = [0 for x in range(n + 1)]
for i in range(1, n + 1):
	we[i] = len(arr[i])
truenode = [x for x in range(n + 1)]

def createtree(pnode, cnode):
	if we[cnode] == 1 and we[pnode] == 1:
		if cnode == 1:
			num = arr[cnode][0]
			createtree(pnode, num)
		else:
			num = arr[cnode][0]
			arr[pnode].remove(cnode)
			arr[pnode].append(num)
			truenode[cnode] = pnode
			createtree(pnode, num)
	elif we[cnode] == 1 and we[pnode] != 1:
		createtree(cnode, arr[cnode][0])
	elif we[cnode] > 1:
		temp = arr[cnode]
		for i in range(len(temp)):
			createtree(cnode, temp[i])
createtree(1, 1)
checkarr = [0 for x in range(n + 1)]

def formcheckingarray(node):
	if we[node] == 0:
		checkarr[node] = 1
		return 1
	pro = 1
	for z in range(we[node]):
		pro *= formcheckingarray(arr[node][z])
	temarr = []
	for z in range(we[node]):
		if we[arr[node][z]] == 0:
			temarr.append(1)
		else:
			temarr.append(we[arr[node][z]])
	temarr = list(set(temarr))
	for z in range(len(temarr)):
		pro *= temarr[z]
	checkarr[node] = pro * we[node]
	return pro
k = formcheckingarray(1)

def solve(node, val):
	if we[node] == 0:
		return 0
	if val % we[node] != 0:
		return val
	elif val % checkarr[node] == 0:
		return 0
	else:
		temarr = arr[node]
		k = 0
		for i in temarr:
			k += solve(i, val // we[node])
		return k
q = int(input())
dict = {}
anode = []
aval = []
for i in range(q):
	(node, val) = map(int, input().split())
	node = truenode[node]
	dict[str([node, val])] = -1
	anode.append(node)
	aval.append(val)
for i in range(q):
	node = anode[i]
	val = aval[i]
	if dict[str([node, val])] == -1:
		ans = solve(node, val)
		dict[str([node, val])] = ans
		print(ans)
	else:
		print(dict[str([node, val])])


n = int(input())
children = [[] for i in range(n + 1)]
for (i, p) in enumerate(input().split(), start=2):
	children[int(p)].append(i)
q = int(input())
memo = dict()

def count(v, w):
	if children[v]:
		if w % len(children[v]) == 0:
			if (v, w) in memo:
				return memo[v, w]
			new_w = w // len(children[v])
			s = 0
			for (i, c) in enumerate(children[v]):
				while len(children[c]) == 1:
					c = children[c][0]
					children[v][i] = c
				s += count(c, new_w)
			memo[v, w] = s
			return s
		else:
			return w
	else:
		return 0
for _ in range(q):
	(v, w) = [int(x) for x in input().split()]
	print(count(v, w))


import os, sys, bisect
from collections import defaultdict, Counter, deque
from functools import lru_cache
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')
input = lambda : sys.stdin.readline().strip()
imap = lambda : map(int, input().split())
ilist = lambda : list(imap())
sys.setrecursionlimit(10 ** 6)
mod = int(1000000000.0 + 7)
n = int(int(input()))
a = list(map(int, input().split()))
q = int(input())
gr = defaultdict(list)
sz = [0] * (n + 1)
for i in range(n - 1):
	gr[a[i]].append(i + 2)
	sz[a[i]] += 1
p = [i for i in range(n + 1)]
par = [i for i in range(n + 1)]

def find(x):
	if x == par[x]:
		return par[x]
	par[x] = find(par[x])
	return par[x]

def union(x, y):
	par[find(y)] = find(x)
qe = deque([1])
while qe:
	s = qe.popleft()
	if sz[s] == 1:
		union(s, gr[s][0])
	for i in gr[s]:
		p[i] = s
		qe.append(i)
prods = [defaultdict(int) for i in range(n + 1)]

def dfs(s):
	if sz[s] == 0:
		prod = 1
		while s != 1 and prod < 10 ** 7:
			prod *= sz[p[s]]
			s = par[p[s]]
			prods[s][prod] += 1
		return
	for i in gr[s]:
		dfs(i)
dfs(1)

def get(s, val):
	if sz[s] == 0:
		return 0
	if val % sz[s]:
		return val
	cnt = 0
	s = par[s]
	for i in prods[s].keys():
		if val % i == 0:
			cnt += val // i * prods[s][i]
	return val - cnt
for _ in range(q):
	(x, y) = map(int, input().split())
	print(get(x, y))


import math, sys
sys.setrecursionlimit(10 ** 6)

def lcm(a, b):
	return a * b // math.gcd(a, b)
cache = {}

def dfs(u):
	for v in adj[u]:
		if v <= n:
			dfs(v)
			subLCM[u] = lcm(subLCM[u], subLCM[v])
	subLCM[u] *= max(1, len(adj[u]))
	if len(adj[u]) == 1:
		shortcut[u] = shortcut[adj[u][0]]

def dfs2(u, task):
	if cache.get(str(u) + '#' + str(task)):
		return cache[str(u) + '#' + str(task)]
	if task % subLCM[u] == 0:
		return 0
	if task % len(adj[u]) != 0:
		return task
	ans = 0
	for v in adj[u]:
		if shortcut[v] <= n:
			ans += dfs2(shortcut[v], task // len(adj[u]))
	cache[str(u) + '#' + str(task)] = ans
	return ans
n = int(input())
par = list(map(int, input().split(' ')))
adj = [[] for i in range(n + 2)]
subLCM = list()
shortcut = list()
for i in range(n + 2):
	subLCM.append(1)
	shortcut.append(i)
for i in range(2, n + 1):
	adj[par[i - 2]].append(i)
dfs(1)
q = int(input())
for i in range(q):
	(v, task) = list(map(int, input().split(' ')))
	print(dfs2(v, task))


import sys
sys.setrecursionlimit(10 ** 5 + 1)
M = 10 ** 5 + 1
vec = []
factor = []
renumbered = []
maxTask = 10 ** 6

def reshape(node):
	if len(vec[node]) == 1:
		return reshape(vec[node][0])
	return vec[node]

def findFactor(node):
	s = len(vec[node])
	if s == 0:
		factor[node][1] = 1
		return
	for i in vec[node]:
		findFactor(i)
		if s != 1:
			for j in factor[renumbered[i]]:
				if s * j <= maxTask:
					if s * j in factor[node]:
						factor[node][s * j] += factor[renumbered[i]][j]
					else:
						factor[node][s * j] = factor[renumbered[i]][j]
	if s == 1:
		renumbered[node] = renumbered[vec[node][0]]

def Task(node, a):
	node = renumbered[node]
	c = 0
	for i in factor[node]:
		if a % i == 0:
			c += int(a / i) * factor[node][i]
	return a - c
n = int(input())
vec = [[] for _ in range(n + 1)]
factor = [{} for _ in range(n + 1)]
vertex = list(map(int, input().split()))
renumbered = [i for i in range(n + 1)]
index = 1
for i in vertex:
	vec[i].append(index + 1)
	index += 1
findFactor(1)
q = int(input())
while q > 0:
	q -= 1
	(v, a) = map(int, input().split())
	print(Task(v, a))


import sys
import math
from collections import deque
sys.setrecursionlimit(100000)
n = int(input())
adj = [[] for i in range(n + 1)]
new_node_id = [i for i in range(n + 1)]
dividing_factor = [{} for i in range(n + 1)]
count_children = [0 for i in range(n + 1)]
parent = [0, 0]
maxW = 1000000

def dfs(node, height):
	has_one_child = False
	if count_children[node] == 1:
		has_one_child = True
	if count_children[node] == 0:
		dividing_factor[node][1] = 1
		return
	for child in adj[node]:
		dfs(child, height + 1)
		if not has_one_child:
			for key in dividing_factor[new_node_id[child]]:
				value = dividing_factor[new_node_id[child]].get(key)
				if key * count_children[node] <= maxW:
					if dividing_factor[node].get(key * count_children[node], -1) == -1:
						dividing_factor[node][key * count_children[node]] = 0
					dividing_factor[node][key * count_children[node]] += value
	if has_one_child:
		new_node_id[node] = new_node_id[adj[node][0]]

def calculate(node, tasks):
	ignored = tasks
	if count_children[node] == 0:
		return 0
	if tasks % count_children[node] == 0:
		for key in dividing_factor[node]:
			if tasks % key == 0:
				ignored -= tasks // key * dividing_factor[node].get(key)
	return ignored
parent = parent + list(map(int, input().split()))
for i in range(2, n + 1):
	adj[parent[i]].append(i)
	count_children[parent[i]] += 1
dfs(1, 1)
Q = int(input())
for _ in range(Q):
	(vertex, task) = list(map(int, input().split()))
	print(calculate(new_node_id[vertex], task))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
N = int(input())
ps = list(map(int, input().split()))
Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]
adj = [[] for _ in range(N + 1)]
d = [{} for _ in range(N + 1)]
for i in range(N - 1):
	adj[ps[i]].append(i + 2)

def dfs(u):
	d_u = d[u]
	if len(adj[u]) == 0:
		d_u[1] = 1
	elif len(adj[u]) == 1:
		dfs(adj[u][0])
		d[u] = d[adj[u][0]]
	else:
		deg = len(adj[u])
		for v in adj[u]:
			dfs(v)
			for key_v in d[v].keys():
				if key_v * deg <= 10 ** 6:
					d_u[key_v * deg] = d_u.get(key_v * deg, 0) + d[v][key_v]
dfs(1)
for [V, W] in queries:
	d_V = d[V]
	sol = W - sum([W // k * d_V[k] for k in d[V].keys() if W % k == 0])
	print(sol)


import sys
from copy import deepcopy
N = int(input())
P = list((int(x) for x in sys.stdin.readline().split()))
children = [0] * (N + 1)
depth = [0] * (N + 1)
depth[1] = 1
child = {}
for j in range(len(P)):
	if P[j] not in child.keys():
		child[P[j]] = []
	child[P[j]].append(j + 2)
	children[P[j]] += 1
	depth[j + 2] = depth[P[j]] + 1
dlist = {}
for node in range(1, N + 1):
	d = depth[node]
	if d in dlist.keys():
		dlist[d].append(node)
	else:
		dlist[d] = [node]
md = max(depth)
prods2 = [-1] * (N + 1)
cnt = 0
for j in range(1, md + 1):
	depth = md + 1 - j
	for node in dlist[depth]:
		cnt += 1
		if node in child.keys():
			cn = child[node]
			if len(cn) == 1:
				prods2[node] = {}
				if -1 in prods2[cn[0]]:
					prods2[node][-1] = prods2[cn[0]][-1]
				else:
					prods2[node][-1] = cn[0]
			else:
				cnt = children[node]
				prods2[node] = {}
				for j in range(cnt):
					if -1 in prods2[cn[j]]:
						target_node = prods2[cn[j]][-1]
						for value in prods2[target_node]:
							v2 = value * cnt
							if v2 <= 1000000:
								if v2 in prods2[node]:
									prods2[node][v2] += prods2[target_node][value]
								else:
									prods2[node][v2] = prods2[target_node][value]
					else:
						for value in prods2[cn[j]]:
							v2 = value * cnt
							if v2 <= 1000000:
								if v2 in prods2[node]:
									prods2[node][v2] += prods2[cn[j]][value]
								else:
									prods2[node][v2] = prods2[cn[j]][value]
		else:
			prods2[node] = {}
			prods2[node][1] = 1
Q = int(input())

def find_waste(n, a):
	used = 0
	curr_node = prods2[n]
	if -1 in prods2[n]:
		index = prods2[n][-1]
		curr_node = prods2[index]
	for value in curr_node:
		if a % value == 0:
			used += curr_node[value] * (a // value)
	return a - used
for q in range(Q):
	(V, W) = list((int(x) for x in sys.stdin.readline().split()))
	print(find_waste(V, W))


import sys
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
li = lambda : list(input_())
pr = lambda x: print(x)
sys.setrecursionlimit(10 ** 6)

def find_lcm(num1, num2):
	if num1 > num2:
		num = num1
		den = num2
	else:
		num = num2
		den = num1
	rem = num % den
	while rem != 0:
		num = den
		den = rem
		rem = num % den
	gcd = den
	lcm = int(int(num1 * num2) / int(gcd))
	return lcm

def change(v):
	x = len(adjlist[v])
	if x == 0:
		return []
	y = []
	for i in adjlist[v]:
		y = change(i)
	if x > 1:
		return []
	elif y == []:
		return [adjlist[v][0]]
	else:
		adjlist[v][0] = y[0]
		return y

def precom(v):
	x = len(adjlist[v])
	if x == 0:
		return 1
	y = 1
	for i in adjlist[v]:
		z = precom(i)
		preval[i] = z
		y = find_lcm(y, z)
	return x * y

def left(v, d):
	x = len(adjlist[v])
	if d % preval[v] == 0:
		return 0
	if e.get(str(v) + ',' + str(d)):
		return e[str(v) + ',' + str(d)]
	if x == 0:
		e[str(v) + ',' + str(d)] = 0
		return 0
	if d % x == 0:
		y = 0
		z = d // x
		for i in adjlist[v]:
			y += left(i, z)
		e[str(v) + ',' + str(d)] = y
		return y
	e[str(v) + ',' + str(d)] = d
	return d
n = ii()
a = il()
q = ii()
adjlist = [[] for i in range(n + 1)]
preval = [1 for i in range(n + 1)]
e = {}
for j in range(n - 1):
	adjlist[a[j]].append(j + 2)
preval[1] = precom(1)
change(1)
for _ in range(q):
	(v, d) = il()
	print(left(v, d))