Blood Cousins Return (Codeforces 246E)
Tags: DP, data structures

Polycarpus got hold of a family tree. The found tree describes the family relations of n people, numbered from 1 to n. Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique.We call the man with a number a a 1-ancestor of the man with a number b, if the man with a number a is a direct ancestor of the man with a number b.We call the man with a number a a k-ancestor (k > 1) of the man with a number b, if the man with a number b has a 1-ancestor, and the man with a number a is a (k - 1)-ancestor of the 1-ancestor of the man with a number b.In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an x-ancestor of himself, for some x, x > 0).We call a man with a number a the k-son of the man with a number b, if the man with a number b is a k-ancestor of the man with a number a.Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote m pairs of numbers vi, ki. Help him to learn for each pair vi, ki the number of distinct names among all names of the ki-sons of the man with number vi.

Input: The first line of the input contains a single integer n (1 ≤ n ≤ 105) — the number of people in the tree. Next n lines contain the description of people in the tree. The i-th line contains space-separated string si and integer ri (0 ≤ ri ≤ n), where si is the name of the man with a number i, and ri is either the number of the direct ancestor of the man with a number i or 0, if the man with a number i has no direct ancestor. The next line contains a single integer m (1 ≤ m ≤ 105) — the number of Polycarpus's records. Next m lines contain space-separated pairs of integers. The i-th line contains integers vi, ki (1 ≤ vi, ki ≤ n).It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than 20 lowercase English letters.

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


Sample Inputs:
6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1

6
valera 0
valera 1
valera 1
gerald 0
valera 4
kolya 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1

Sample Outputs:
2
2
0
1
0

1
0
0
0
2
0
0

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def dsu_on_tree(N, G, s0, PropDS):
    order = []
    prt = [-1] * N
    depth = [-1] * N
    que = [s0]
    pn = [-1] * N
    used = [0] * N
    used[s0] = 1
    depth[s0] = 0
    while que:
        v = que.pop()
        d = depth[v] + 1
        for w in G[v]:
            if used[w]:
                continue
            used[w] = 1
            que.append(w)
            prt[w] = v
            depth[w] = d
        pn[v] = len(order)
        order.append(v)
    sz = [0] * N
    tmp_ps = [[i] for i in range(N)]
    h_ps = []
    for v in reversed(order):
        p = prt[v]
        m_sz = 0
        h = -1
        s = 1
        for w in G[v]:
            if p == w:
                continue
            if m_sz < sz[w]:
                m_sz = sz[w]
                h = w
            s += sz[w]
        if h != -1:
            tmp_ps[v] = tmp_ps[h]
            tmp_ps[v].append(v)
            for w in G[v]:
                if w == p or w == h:
                    continue
                h_ps.append(tmp_ps[w])
        sz[v] = s
    h_ps.append(tmp_ps[s0])
    ph = PropDS(depth)
    for path in h_ps:
        h = -1
        for v in path:
            p = prt[v]
            for w in G[v]:
                if w == p or w == h:
                    continue
                for c in order[pn[w]:pn[w] + sz[w]]:
                    ph.add(c)
            ph.add(v)
            ph.query(v)
            h = v
        ph.reset()

def solve():
    N = int(readline())
    G = [[] for i in range(N + 1)]
    prt = [-1] * N
    names = [None] * N
    lbs = [-1] * (N + 1)
    ns = set()
    for i in range(N):
        (name, r) = readline().split()
        r = int(r)
        if r == 0:
            s = i
            prt[i] = N
            G[N].append(i)
        else:
            prt[i] = r - 1
            G[r - 1].append(i)
        names[i] = name
        ns.add(name)
    mp = {name: i for (i, name) in enumerate(ns)}
    lbs[:N] = map(mp.__getitem__, names)
    M = int(readline())
    qs = [[] for i in range(N + 1)]
    for i in range(M):
        (v, k) = map(int, readline().split())
        qs[v - 1].append((k, i))
    ans = [0] * M

    class PropDS:

        def __init__(self, depth):
            self.sets = [set() for i in range(N + 1)]
            self.depth = depth
            self.us = set()

        def add(self, v):
            d = self.depth[v]
            self.sets[d].add(lbs[v])
            self.us.add(d)

        def reset(self):
            for u in self.us:
                self.sets[u].clear()
            self.us.clear()

        def query(self, v):
            d = self.depth[v]
            for (k, i) in qs[v]:
                if d + k < N + 1:
                    ans[i] = len(self.sets[d + k])
    dsu_on_tree(N + 1, G, N, PropDS)
    for i in range(M):
        write('%d\n' % ans[i])
solve()

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def dsu_on_tree(N, G, s0, PropDS):
    order = []
    prt = [-1] * N
    depth = [-1] * N
    que = [s0]
    pn = [-1] * N
    used = [0] * N
    used[s0] = 1
    depth[s0] = 0
    while que:
        v = que.pop()
        d = depth[v] + 1
        for w in G[v]:
            if used[w]:
                continue
            used[w] = 1
            que.append(w)
            prt[w] = v
            depth[w] = d
        pn[v] = len(order)
        order.append(v)
    sz = [0] * N
    tmp_ps = [[i] for i in range(N)]
    h_ps = []
    for v in reversed(order):
        p = prt[v]
        m_sz = 0
        h = -1
        s = 1
        for w in G[v]:
            if p == w:
                continue
            if m_sz < sz[w]:
                m_sz = sz[w]
                h = w
            s += sz[w]
        if h != -1:
            tmp_ps[v] = tmp_ps[h]
            tmp_ps[v].append(v)
            for w in G[v]:
                if w == p or w == h:
                    continue
                h_ps.append(tmp_ps[w])
        sz[v] = s
    h_ps.append(tmp_ps[s0])
    ph = PropDS(depth)
    for path in h_ps:
        h = -1
        for v in path:
            p = prt[v]
            for w in G[v]:
                if w == p or w == h:
                    continue
                for c in order[pn[w]:pn[w] + sz[w]]:
                    ph.add(c)
            ph.add(v)
            ph.query(v)
            h = v
        ph.reset()

def solve():
    N = int(readline())
    G = [[] for i in range(N + 1)]
    prt = [-1] * N
    names = [None] * N
    lbs = [-1] * (N + 1)
    ns = set()
    for i in range(N):
        (name, r) = readline().split()
        r = int(r)
        if r == 0:
            s = i
            prt[i] = N
            G[N].append(i)
        else:
            prt[i] = r - 1
            G[r - 1].append(i)
        names[i] = name
        ns.add(name)
    mp = {name: i for (i, name) in enumerate(ns)}
    lbs[:N] = map(mp.__getitem__, names)
    M = int(readline())
    qs = [[] for i in range(N + 1)]
    for i in range(M):
        (v, k) = map(int, readline().split())
        qs[v - 1].append((k, i))
    ans = [0] * M

    class PropDS:

        def __init__(self, depth):
            self.sets = [set() for i in range(N + 1)]
            self.depth = depth
            self.us = set()

        def add(self, v):
            d = self.depth[v]
            self.sets[d].add(lbs[v])
            self.us.add(d)

        def reset(self):
            for u in self.us:
                self.sets[u].clear()
            self.us.clear()

        def query(self, v):
            d = self.depth[v]
            for (k, i) in qs[v]:
                if d + k < N + 1:
                    ans[i] = len(self.sets[d + k])
    dsu_on_tree(N + 1, G, N, PropDS)
    for i in range(M):
        write('%d\n' % ans[i])
solve()

Solution (Python):
import sys, math
from bisect import bisect_left, bisect_right

def rd():
    return sys.stdin.readline().strip()

def rdl(typ, sep=' '):
    return list(map(typ, rd().split(sep)))

def wt(x, sep='\n'):
    sys.stdout.write(str(x) + sep)

def wtBoolUp(x):
    wt('YES' if x else 'NO')

def wtBoolLow(x):
    wt('Yes' if x else 'No')

def wtlArr(arr, sep=' '):
    if not arr:
        return
    for x in arr:
        wt(x, ' ')

def wtlsArr(arr):
    if not arr:
        return
    for x in arr:
        wt(x)

def wtlsArrArr(arr):
    for a in arr:
        wtlArr(a)
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
INF = 10 ** 18
mod = 10 ** 9 + 7

def binPow(a, b, mod):
    res = 1
    while b:
        if b % 2:
            res = res * a % mod
        a = a * a % mod
        b //= 2
    return res

def invMod(x, mod):
    return pow(x, mod - 2, mod)

def getFacts(n, mod):
    fact = [1] * (n + 1)
    for i in range(2, n + 1):
        fact[i] = i * fact[i - 1] % mod
    return fact

def nCr(n, r, fact, mod):
    num = fact[n]
    den = fact[r] * fact[n - r] % mod
    return num * invMod(den, mod) % mod

def lcm(num1, num2):
    hcf = math.gcd(num1, num2)
    lcm_ = num1 * num2 // hcf
    return lcm_

def sqrtFloat(num):
    (l, r) = (0, num)
    res = 0
    while l <= r:
        mid = (l + r) // 2
        if mid * mid <= num:
            res = mid
            l = mid + 1
        else:
            r = mid - 1
    return res + 0.1 * (res * res != num)

def floor(a, b):
    return a // b

def ceil(a, b):
    return (a + b - 1) // b

def prefixSum(arr):
    pref = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        pref[i] = arr[i] + pref[i - 1]
    return pref

def prefixXor(arr):
    pref = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        pref[i] = arr[i] ^ pref[i - 1]
    return pref

def apNth(n, a=1, d=1):
    return a + (n - 1) * d

def apSum(n, a=1, d=1):
    return (2 * a + (n - 1) * d) * n // 2

def apSumRange(l, r, d=1):
    return apSum((r - l + 1) // d, l, d)

def hypot(p1, p2):
    return ((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2) ** 0.5

def manhat(p1, p2):
    return abs(p2[0] - p1[0]) + abs(p2[1] - p1[1])

def comb(n, r):
    res = 1
    for i in range(r):
        res = res * (n - i) // (i + 1)
    return res

def powerArr(base, n, mod):
    pwr = [1] * n
    for i in range(1, n):
        pwr[i] = base * pwr[i - 1] % mod
    return pwr

def getClosest(num, sortArr, notTake=-INF, notTakeCnt=1):
    idx = bisect_left(sortArr, num)
    closeArr = []
    for i in range(max(0, idx - 2), min(len(sortArr), idx + 3)):
        if notTakeCnt > 0 and sortArr[i] == notTake:
            notTakeCnt -= 1
            continue
        closeArr.append(sortArr[i])
    return min(closeArr, key=lambda x: abs(x - num), default=-INF)

def grouping(arr, notTake=INF):
    n = len(arr)
    res = []
    i = 0
    while i < n:
        st = i
        while i + 1 < n and arr[i] == arr[i + 1]:
            i += 1
        if arr[st] != notTake:
            res.append([arr[st], st, i, i - st + 1])
        i += 1
    return res

def dirnsRD():
    return [(0, 1), (1, 0)]

def dirnsLU():
    return [(0, -1), (-1, 0)]

def dirns():
    return dirnsRD() + dirnsLU()

def dirnsDiag():
    return dirns() + [(1, 1), (1, -1), (-1, 1), (-1, -1)]

def chessDirns():
    return [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

def cntBits(n):
    return bin(n).count('1')

def isRepSumP2(num, x):
    return cntBits(num) <= x <= num

def binry(decimal):
    return bin(decimal).replace('0b', '')

def deciml(binary):
    return int(str(binary), 2)

def printAllBin(arr):
    maxLen = len(binry(max(arr)))
    for x in arr:
        curr = binry(x)
        res = ' '.join(list('0' * (maxLen - len(curr)) + curr))
        wt(res + f'   <- {x}')

def c2i(ch, up=0):
    return ord(ch) - ord('A' if up else 'a')

def i2c(n, up=0):
    return chr(ord('A' if up else 'a') + n)

def setPrec(num, cnt):
    return round(num, cnt)

def flush():
    sys.stdout.flush()

def clearCache(func):
    func.cache_clear()
''
adjList = queries = name = res = parent = []

def merge(rootMap, childMap):
    if len(rootMap) < len(childMap):
        (rootMap, childMap) = (childMap, rootMap)
    for lvl in childMap:
        if lvl not in rootMap:
            rootMap[lvl] = childMap[lvl]
            continue
        rootMap[lvl].update(childMap[lvl])
    return rootMap

@bootstrap
def dfs(root, par, dep):
    rootMap = {dep: {name[root]}}
    for child in adjList[root]:
        parent[child] = root
        if child == par:
            continue
        childMap = (yield dfs(child, root, dep + 1))
        rootMap = merge(rootMap, childMap)
    for (qIdx, k) in queries[root]:
        ddep = k + dep
        res[qIdx] = len(rootMap.get(ddep, {}))
    yield rootMap

def solve():
    global adjList, queries, name, res, parent
    n = int(rd())
    name = [None] * (n + 1)
    adjList = [[] for _ in range(n + 1)]
    for i in range(n):
        (name[i], par) = rdl(str)
        par = int(par) - 1
        if par != -1:
            adjList[par].append(i)
    queries = [[] for _ in range(n + 1)]
    m = int(rd())
    for qIdx in range(m):
        (node, k) = rdl(int)
        node = int(node) - 1
        queries[node].append((qIdx, k))
    parent = [-1] * (n + 1)
    res = [0] * m
    for i in range(n):
        if parent[i] != -1:
            continue
        dfs(i, -1, 0)
    wtlsArr(res)
solve()