Tree and Queries (Codeforces 375D)
Tags: Others, trees

You have a rooted tree consisting of n vertices. Each vertex of the tree has some color. We will assume that the tree vertices are numbered by integers from 1 to n. Then we represent the color of vertex v as cv. The tree root is a vertex with number 1.In this problem you need to answer to m queries. Each query is described by two integers vj, kj. The answer to query vj, kj is the number of such colors of vertices x, that the subtree of vertex vj contains at least kj vertices of color x.You can find the definition of a rooted tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory).

Input: The first line contains two integers n and m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105). The next line contains a sequence of integers c1, c2, ..., cn (1 ≤ ci ≤ 105). The next n - 1 lines contain the edges of the tree. The i-th line contains the numbers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.Next m lines contain the queries. The j-th line contains two integers vj, kj (1 ≤ vj ≤ n; 1 ≤ kj ≤ 105).

Output: Print m integers — the answers to the queries in the order the queries appear in the input.

Note: A subtree of vertex v in a rooted tree with root r is a set of vertices {u : dist(r, v) + dist(v, u) = dist(r, u)}. Where dist(x, y) is the length (in edges) of the shortest path between vertices x and y.

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

4 1
1 2 3 4
1 2
2 3
3 4
1 1

Sample Outputs:
2
2
1
0
1

4

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

def Mo(N, Q, query):
    D = max(1, int(N / Q ** 0.5))
    mo = [[] for d in range((N + D - 1) // D + 1)]
    for (q, (l, r)) in enumerate(query):
        mo[l // D].append(q)
    retu = []
    for d in range((N + D - 1) // D + 1):
        retu += sorted(mo[d], reverse=d % 2, key=lambda q: query[q][1])
    return retu
(N, Q) = map(int, readline().split())
C = list(map(int, readline().split()))
graph = [[] for x in range(N)]
for _ in range(N - 1):
    (a, b) = map(int, readline().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
seen = [False] * N
finished = [False] * N
stack = [0]
tour = []
size = [1] * N
while stack:
    x = stack.pop()
    if not seen[x]:
        tour.append(x)
        seen[x] = True
        stack.append(x)
        for y in graph[x]:
            if not seen[y]:
                stack.append(y)
    elif not finished[x]:
        finished[x] = True
        for y in graph[x]:
            if finished[y]:
                size[x] += size[y]
query = []
for m in range(Q):
    (v, k) = map(int, readline().split())
    v -= 1
    query.append((v, k))
idx = [None] * N
for i in range(N):
    idx[tour[i]] = i
M = max(C)
C = [C[x] for x in tour]
(L, R) = (0, 0)
cnt = [0] * (M + 1)
freq = [0] * (10 ** 5 + 1)
ans_lst = [None] * Q
for q in Mo(N, Q, [(idx[v], idx[v] + size[v]) for (v, _) in query]):
    (v, k) = query[q]
    (l, r) = (idx[v], idx[v] + size[v])
    while l < L:
        L -= 1
        freq[cnt[C[L]] + 1] += 1
        cnt[C[L]] += 1
    while R < r:
        cnt[C[R]]
        freq[cnt[C[R]] + 1] += 1
        cnt[C[R]] += 1
        R += 1
    while L < l:
        cnt[C[L]] -= 1
        freq[cnt[C[L]] + 1] -= 1
        L += 1
    while r < R:
        R -= 1
        cnt[C[R]] -= 1
        freq[cnt[C[R]] + 1] -= 1
    ans_lst[q] = freq[k]
print(*ans_lst, sep='\n')

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

def dsu_on_tree(N, G, PropDS):
    order = []
    prt = [-1] * N
    que = [0]
    pn = [-1] * N
    used = [0] * N
    used[0] = 1
    while que:
        v = que.pop()
        for w in G[v]:
            if used[w]:
                continue
            used[w] = 1
            que.append(w)
            prt[w] = v
        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[0])
    ans = [-1] * N
    ph = PropDS()
    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)
            ans[v] = ph.get(v)
            h = v
        for c in order[pn[v]:pn[v] + sz[v]]:
            ph.remove(c)
    return ans

def solve():
    (N, M) = map(int, readline().split())
    (*C,) = map(int, readline().split())
    G = [[] for i in range(N)]
    for i in range(N - 1):
        (s, t) = map(int, readline().split())
        G[s - 1].append(t - 1)
        G[t - 1].append(s - 1)
    qs = [[] for i in range(N)]
    for i in range(M):
        (v, k) = map(int, readline().split())
        qs[v - 1].append((k, i))
    L = 10 ** 5
    ans = [0] * M

    class PropDS:

        def __init__(self):
            self.ct = [0] * L
            self.res = 0
            self.data = [0] * (L + 1)
            self.__add(1, L)

        def __add(self, k, x):
            data = self.data
            while k <= L:
                data[k] += x
                k += k & -k

        def __get(self, k):
            data = self.data
            s = 0
            while k > 0:
                s += data[k]
                k -= k & -k
            return s

        def add(self, v):
            c = C[v] - 1
            e = self.ct[c]
            self.ct[c] = e + 1
            self.__add(e + 1, -1)
            self.__add(e + 2, 1)

        def remove(self, v):
            c = C[v] - 1
            e = self.ct[c]
            self.ct[c] = e - 1
            self.__add(e + 1, -1)
            self.__add(e, 1)

        def get(self, v):
            for (k, i) in qs[v]:
                ans[i] = L - self.__get(k)
    dsu_on_tree(N, G, PropDS)
    for i in range(M):
        write('%d\n' % ans[i])
solve()

Solution (Python):
import os, sys, math, random, threading
from copy import deepcopy
from io import BytesIO, IOBase
from types import GeneratorType
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
import types
BUFSIZE = 4096

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 = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
mod = int(1000000000.0 + 7)
inf = int(1e+20)
input = lambda : sys.stdin.readline().rstrip('\r\n')
MI = lambda : map(int, input().split())
li = lambda : list(MI())
ii = lambda : int(input())
py = lambda : print('YES')
pn = lambda : print('NO')
ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]

class BIT1:
    """"""
    __slots__ = ('size', 'bit', 'tree')

    def __init__(self, n: int):
        self.size = n
        self.bit = n.bit_length()
        self.tree = [0] * (n + 1)

    def add(self, index: int, delta: int) -> None:
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def _query(self, index: int) -> int:
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= index & -index
        return res

    def query(self, left: int, right: int) -> int:
        return self._query(right) - self._query(left - 1)

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

class HLD:

    def __init__(self, g, root):
        n = len(g)
        self.g = g
        self.fa = [0] * (n + 5)
        self.size = [1] * (n + 5)
        self.dep = [0] * (n + 5)
        self.son = [0] * (n + 5)
        self.dfn = [0] * (n + 5)
        self.top = [0] * (n + 5)
        self.rank = [0] * (n + 5)
        fa = self.fa
        size = self.size
        dep = self.dep
        son = self.son
        dfn = self.dfn
        top = self.top
        rank = self.rank
        stk = [[root, 0, 0]]
        dep[root] = 1
        while stk:
            (u, flag, father) = stk.pop()
            if flag:
                for v in g[u]:
                    if v != father:
                        size[u] += size[v]
                        if son[u] == 0 or size[v] > size[son[u]]:
                            son[u] = v
            else:
                stk.append([u, 1, father])
                for v in g[u]:
                    if v != father:
                        stk.append([v, 0, u])
                        fa[v] = u
                        dep[v] = dep[u] + 1
        stk = [[root, root]]
        tot = 1
        while stk:
            (u, tops) = stk.pop()
            dfn[u] = tot
            rank[tot] = u
            tot += 1
            top[u] = tops
            if son[u] == 0:
                continue
            for v in g[u]:
                if v != fa[u] and v != son[u]:
                    stk.append([v, v])
            stk.append([son[u], tops])
(n, q) = li()
node = [0] + li()
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    (u, v) = li()
    g[u] += [v]
    g[v] += [u]
hld = HLD(g, 1)
dfn = hld.dfn
size = hld.size
son = hld.son
rank = hld.rank
res = [0] * q
query = [[] for _ in range(n + 1)]
for i in range(q):
    (u, k) = li()
    query[u].append([i, k])
col = [0] * (10 ** 5 + 5)
cnt = [0] * (10 ** 5 + 5)

@bootstrap
def dfs(u, fa, flag):
    for v in g[u]:
        if v != fa and v != son[u]:
            yield dfs(v, u, False)
    if son[u] != 0:
        yield dfs(son[u], u, True)
    for v in g[u]:
        if v != fa and v != son[u]:
            for i in range(dfn[v], dfn[v] + size[v]):
                x = rank[i]
                col[node[x]] += 1
                cnt[col[node[x]]] += 1
    col[node[u]] += 1
    cnt[col[node[u]]] += 1
    for (idx, k) in query[u]:
        res[idx] = cnt[k]
    if not flag:
        for i in range(dfn[u], dfn[u] + size[u]):
            x = rank[i]
            cnt[col[node[x]]] -= 1
            col[node[x]] -= 1
    yield None
dfs(1, -1, False)
for i in range(q):
    print(res[i])