Blood Cousins (Codeforces 208E)
Tags: Others, trees

Polycarpus got hold of a family relationship tree. The tree describes family relationships of n people, numbered 1 through n. Each person in the tree has no more than one parent.Let's call person a a 1-ancestor of person b, if a is the parent of b.Let's call person a a k-ancestor (k > 1) of person b, if person b has a 1-ancestor, and a is a (k - 1)-ancestor of b's 1-ancestor. Family relationships don't form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an x-ancestor for himself, for some x, x > 0).Let's call two people x and y (x ≠ y) p-th cousins (p > 0), if there is person z, who is a p-ancestor of x and a p-ancestor of y.Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote m pairs of integers vi, pi. Help him to calculate the number of pi-th cousins that person vi has, for each pair vi, pi.

Input: The first input line contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. The next line contains n space-separated integers r1, r2, ..., rn, where ri (1 ≤ ri ≤ n) is the number of person i's parent or 0, if person i has no parent. It is guaranteed that family relationships don't form cycles.The third line contains a single number m (1 ≤ m ≤ 105) — the number of family relationship queries Polycarus has. Next m lines contain pairs of space-separated integers. The i-th line contains numbers vi, pi (1 ≤ vi, pi ≤ n).

Output: Print m space-separated integers — the answers to Polycarpus' queries. Print the answers to the queries in the order, in which the queries occur in the input.


Sample Inputs:
6
0 1 1 0 4 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1

Sample Outputs:
0 0 1 0 0 1 1

Solution (Python):
import decimal
import gc
import heapq
import math
import operator
import os
import random
import sys
from collections import Counter, deque, defaultdict, OrderedDict
from copy import copy
from fractions import Fraction
from io import BytesIO, IOBase
import bisect
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        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

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 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 = os.read(self._fd, max(os.fstat(self._fd).st_size, 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:
            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 bucketsort(order, seq):
    buckets = [0] * (max(seq) + 1)
    for x in seq:
        buckets[x] += 1
    for i in range(len(buckets) - 1):
        buckets[i + 1] += buckets[i]
    new_order = [-1] * len(seq)
    for i in reversed(order):
        x = seq[i]
        idx = buckets[x] = buckets[x] - 1
        new_order[idx] = i
    return new_order

def ordersort(order, seq, reverse=False):
    bit = max(seq).bit_length() >> 1
    mask = (1 << bit) - 1
    order = bucketsort(order, [x & mask for x in seq])
    order = bucketsort(order, [x >> bit for x in seq])
    if reverse:
        order.reverse()
    return order

def isPrime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True

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

def ciel(a, b):
    x = a // b
    if a % b == 0:
        return x
    return x + 1

def ints_get():
    return map(int, input().strip().split())

def list_get():
    return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
    return list(map(str, sys.stdin.readline().strip().split()))

def ipn():
    return int(input())

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 main():
    n = ipn()
    r = list_get()
    sp = [[0]]
    for i in range(n):
        sp.append([r[i]])
    for _ in range(32):
        for i in range(n + 1):
            sp[i].append(sp[sp[i][-1]][len(sp[i]) - 1])
    d = defaultdict(list)
    for i in range(n):
        d[i + 1].append(r[i])
        d[r[i]].append(i + 1)
    tin = [-1] * (n + 1)
    tout = [-1] * (n + 1)
    val = [0]
    dic1 = defaultdict(list)
    dic2 = defaultdict(list)
    d2 = defaultdict(lambda : -1)

    @bootstrap
    def dfs(s, e, cur):
        val[0] += 1
        d2[s] = cur
        tin[s] = val[0]
        for u in d[s]:
            if u == e:
                continue
            yield dfs(u, s, cur + 1)
        val[0] += 1
        tout[s] = val[0]
        dic1[cur].append(tin[s])
        dic2[cur].append(tout[s])
        yield
    dfs(0, -1, 0)
    res = []
    for _ in range(ipn()):
        (a, b) = ints_get()
        for k in range(32):
            if b & pow(2, k) > 0:
                a = sp[a][k]
        if a == 0:
            res.append(0)
        else:
            val = d2[a]
            p = bisect.bisect_left(dic1[val + b], tin[a])
            q = bisect.bisect_left(dic2[val + b], tout[a])
            res.append(q - p - 1)
    print(*res)
    return
if __name__ == '__main__':
    main()

Solution (Python):
import bisect
import heapq
import sys
from types import GeneratorType
from functools import cmp_to_key
from collections import defaultdict, Counter, deque
import math
from functools import lru_cache
from heapq import nlargest
from functools import reduce
import random
from itertools import combinations
from itertools import accumulate
from operator import xor, add
from operator import mul
from typing import List
inf = float('inf')
PLATFORM = 'CF'
if PLATFORM == 'LUOGU':
    import numpy as np
    sys.setrecursionlimit(1000000)

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return float(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(' '.join((str(w) for w in x)) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, queue=[]):

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

class DFS:

    def __init__(self):
        return

    @staticmethod
    def gen_dfs_order_recursion(dct):

        def dfs(x):
            nonlocal order
            start[x] = order
            order += 1
            for y in dct[x]:
                if start[y] == -1:
                    dfs(y)
            end[x] = order - 1
            return
        n = len(dct)
        order = 0
        start = [-1] * n
        end = [-1] * n
        dfs(0)
        return (start, end)

    @staticmethod
    def gen_dfs_order_iteration(dct):
        n = len(dct)
        order = 0
        start = [-1] * n
        end = [-1] * n
        parent = [-1] * n
        stack = [[0, 1, -1, 0]]
        depth = [0] * n
        while stack:
            (i, state, fa, d) = stack.pop()
            if state:
                start[i] = order
                end[i] = order
                depth[i] = d
                order += 1
                stack.append([i, 0, fa, d])
                for j in dct[i]:
                    if j != fa:
                        parent[j] = i
                        stack.append([j, 1, i, d + 1])
            elif parent[i] != -1:
                end[parent[i]] = end[i]
        return (start, end, depth)

class TreeAncestor:

    def __init__(self, edges: List[List[int]]):
        n = len(edges)
        self.parent = [-1] * n
        self.depth = [-1] * n
        stack = deque([0])
        self.depth[0] = 0
        while stack:
            i = stack.popleft()
            for j in edges[i]:
                if self.depth[j] == -1:
                    self.depth[j] = self.depth[i] + 1
                    self.parent[j] = i
                    stack.append(j)
        self.cols = max(2, math.ceil(math.log2(n)))
        self.dp = [[-1] * self.cols for _ in range(n)]
        for i in range(n):
            self.dp[i][0] = self.parent[i]
        for j in range(1, self.cols):
            for i in range(n):
                father = self.dp[i][j - 1]
                if father != -1:
                    self.dp[i][j] = self.dp[father][j - 1]
        return

    def get_kth_ancestor(self, node: int, k: int) -> int:
        for i in range(self.cols - 1, -1, -1):
            if k & 1 << i:
                node = self.dp[node][i]
                if node == -1:
                    break
        return node

    def get_lca(self, x: int, y: int) -> int:
        if self.depth[x] < self.depth[y]:
            (x, y) = (y, x)
        while self.depth[x] > self.depth[y]:
            d = self.depth[x] - self.depth[y]
            x = self.dp[x][int(math.log2(d))]
        if x == y:
            return x
        for k in range(int(math.log2(self.depth[x])), -1, -1):
            if self.dp[x][k] != self.dp[y][k]:
                x = self.dp[x][k]
                y = self.dp[y][k]
        return self.dp[x][0]

    def get_dist(self, u: int, v: int) -> int:
        lca = self.get_lca(u, v)
        depth_u = self.depth[u]
        depth_v = self.depth[v]
        depth_lca = self.depth[lca]
        return depth_u + depth_v - 2 * depth_lca

class Solution:

    def __init__(self):
        return

    @staticmethod
    def main(ac=FastIO()):
        n = ac.read_int()
        parent = ac.read_list_ints()
        edge = [[] for _ in range(n + 1)]
        for i in range(n):
            edge[parent[i]].append(i + 1)
            edge[i + 1].append(parent[i])
        del parent
        tree = TreeAncestor(edge)
        (start, end, _) = DFS().gen_dfs_order_iteration(edge)
        dct = [[] for _ in range(n + 1)]
        for i in range(n + 1):
            dct[tree.depth[i]].append(start[i])
        for i in range(n + 1):
            dct[i].sort()
        ans = []
        for _ in range(ac.read_int()):
            (v, p) = ac.read_ints()
            if tree.depth[v] - 1 < p:
                ans.append(0)
                continue
            u = tree.get_kth_ancestor(v, p)
            (low, high) = (start[u], end[u])
            cur = bisect.bisect_right(dct[tree.depth[v]], high) - bisect.bisect_left(dct[tree.depth[v]], low)
            ans.append(ac.max(cur - 1, 0))
        ac.lst(ans)
        return
Solution().main()

Solution (Python):
import sys
import random
input = sys.stdin.readline
rd = random.randint(10 ** 9, 2 * 10 ** 9)
n = int(input())
p = list(map(int, input().split()))
g = [[] for _ in range(n)]
for i in range(n):
    if p[i] == 0:
        continue
    g[p[i] - 1].append(i)
q = int(input())
queries = [[] for _ in range(n)]
queries2 = [[] for _ in range(n)]
ans = [0] * q
for i in range(q):
    (x, d) = map(int, input().split())
    queries[x - 1].append((d, i))
from collections import defaultdict
path = []
from types import GeneratorType

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

@bootstrap
def dfs(son, depth):
    ds = defaultdict(int)
    ds[depth] += 1
    path.append(son)
    for (d, i) in queries[son]:
        if d > depth:
            continue
        queries2[path[-d - 1]].append((d, i))
    for x in g[son]:
        dx = (yield dfs(x, depth + 1))
        if len(dx) > len(ds):
            (ds, dx) = (dx, ds)
        for (k, v) in dx.items():
            ds[k] += v
        dx.clear()
    for (d, i) in queries2[son]:
        ans[i] = ds[d + depth] - 1
    path.pop()
    yield ds
for i in range(n):
    if p[i] == 0:
        dfs(i, 0)
print(*ans)