Tree Queries (Codeforces 1606F)
Tags: DP, trees

You are given a tree consisting of $$$n$$$ vertices. Recall that a tree is an undirected connected acyclic graph. The given tree is rooted at the vertex $$$1$$$.You have to process $$$q$$$ queries. In each query, you are given a vertex of the tree $$$v$$$ and an integer $$$k$$$.To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex $$$v$$$. When a vertex is deleted, its children become the children of its parent. You have to process a query in such a way that maximizes the value of $$$c(v) - m \cdot k$$$ (where $$$c(v)$$$ is the resulting number of children of the vertex $$$v$$$, and $$$m$$$ is the number of vertices you have deleted). Print the maximum possible value you can obtain.The queries are independent: the changes you make to the tree while processing a query don't affect the tree in other queries.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.Then $$$n-1$$$ lines follow, the $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge. These edges form a tree.The next line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.Then $$$q$$$ lines follow, the $$$j$$$-th of them contains two integers $$$v_j$$$ and $$$k_j$$$ ($$$1 \le v_j \le n$$$; $$$0 \le k_j \le 2 \cdot 10^5$$$) — the parameters of the $$$j$$$-th query.

Output: For each query, print one integer — the maximum value of $$$c(v) - m \cdot k$$$ you can achieve.

Note: The tree in the first example is shown in the following picture:  Answers to the queries are obtained as follows:  $$$v=1,k=0$$$: you can delete vertices $$$7$$$ and $$$3$$$, so the vertex $$$1$$$ has $$$5$$$ children (vertices $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$, and $$$8$$$), and the score is $$$5 - 2 \cdot 0 = 5$$$;  $$$v=1,k=2$$$: you can delete the vertex $$$7$$$, so the vertex $$$1$$$ has $$$4$$$ children (vertices $$$3$$$, $$$4$$$, $$$5$$$, and $$$6$$$), and the score is $$$4 - 1 \cdot 2 = 2$$$.  $$$v=1,k=3$$$: you shouldn't delete any vertices, so the vertex $$$1$$$ has only one child (vertex $$$7$$$), and the score is $$$1 - 0 \cdot 3 = 1$$$;  $$$v=7,k=1$$$: you can delete the vertex $$$3$$$, so the vertex $$$7$$$ has $$$5$$$ children (vertices $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$, and $$$8$$$), and the score is $$$5 - 1 \cdot 1 = 4$$$;  $$$v=5,k=0$$$: no matter what you do, the vertex $$$5$$$ will have no children, so the score is $$$0$$$;  $$$v=7,k=200000$$$: you shouldn't delete any vertices, so the vertex $$$7$$$ has $$$4$$$ children (vertices $$$3$$$, $$$4$$$, $$$5$$$, and $$$6$$$), and the score is $$$4 - 0 \cdot 200000 = 4$$$. 

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

Sample Outputs:
5
2
1
4
0
4

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph1(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def make_graph2(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = [s]
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [-1] * (n + 1)
    for i in q:
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return (q, parent)

def f(u, v):
    return 135 * u + v
n = int(input())
(G, s0) = make_graph1(n, n - 1)
(p, parent) = bfs(1)
q = int(input())
(x, v0, k0) = ([0] * (2 * q), [0] * q, [0] * q)
for i in range(q):
    (v, k) = map(int, input().split())
    (x[2 * i], x[2 * i + 1]) = (k, i)
    (v0[i], k0[i]) = (v, k)
m = 200005
(Q1, s1) = make_graph2(m, q)
for i in range(q):
    x[2 * i] = v0[i]
(Q2, s2) = make_graph2(n, q)
p = p[::-1]
ans = [0] * q
for k in range(1500):
    if s1[k] == s1[k + 1]:
        continue
    dp = [0] * (n + 1)
    for i in p[:-1]:
        dp[parent[i]] += max(1, dp[i] - k)
    for w in range(s1[k], s1[k + 1]):
        i = Q1[w]
        v = v0[i]
        ans[i] = dp[v]
dp = [0] * (135 * (n + 1))
cnt = [1] * (n + 1)
for i in p:
    dp0 = [0] * 135
    for v in range(s0[i], s0[i + 1]):
        j = G[v]
        if parent[i] == j:
            continue
        dp1 = [k + 1 for k in dp0]
        for k in range(min(cnt[j], 134)):
            dpk = dp[f(j, k)]
            for l in range(min(cnt[i], 134 - k)):
                dp1[k + l + 1] = max(dp1[k + l + 1], dpk + dp0[l])
        cnt[i] += cnt[j]
        dp0 = dp1
    j = 135 * i
    for k in range(135):
        dp[j + k] = dp0[k]
    for w in range(s2[i], s2[i + 1]):
        j = Q2[w]
        k = k0[j]
        ans0 = ans[j]
        for m in range(135):
            ans0 = max(ans0, dp0[m] - m * k)
        ans[j] = ans0
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph1(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def make_graph2(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = [s]
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [-1] * (n + 1)
    for i in q:
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return (q, parent)

def f(u, v):
    return 101 * u + v
n = int(input())
(G, s0) = make_graph1(n, n - 1)
(p, parent) = bfs(1)
q = int(input())
(x, v0, k0) = ([0] * (2 * q), [0] * q, [0] * q)
for i in range(q):
    (v, k) = map(int, input().split())
    (x[2 * i], x[2 * i + 1]) = (k, i)
    (v0[i], k0[i]) = (v, k)
m = 200005
(Q1, s1) = make_graph2(m, q)
for i in range(q):
    x[2 * i] = v0[i]
(Q2, s2) = make_graph2(n, q)
p = p[::-1]
ans = [0] * q
for k in range(2000):
    if s1[k] == s1[k + 1]:
        continue
    dp = [0] * (n + 1)
    for i in p[:-1]:
        dp[parent[i]] += max(1, dp[i] - k)
    for w in range(s1[k], s1[k + 1]):
        i = Q1[w]
        v = v0[i]
        ans[i] = dp[v]
dp = [0] * (101 * (n + 1))
cnt = [1] * (n + 1)
for i in p:
    dp0 = [0] * 101
    for v in range(s0[i], s0[i + 1]):
        j = G[v]
        if parent[i] == j:
            continue
        dp1 = [k + 1 for k in dp0]
        for k in range(min(cnt[j], 100)):
            dpk = dp[f(j, k)]
            for l in range(min(cnt[i], 100 - k)):
                dp1[k + l + 1] = max(dp1[k + l + 1], dpk + dp0[l])
        cnt[i] += cnt[j]
        dp0 = dp1
    j = 101 * i
    for k in range(101):
        dp[j + k] = dp0[k]
    for w in range(s2[i], s2[i + 1]):
        j = Q2[w]
        k = k0[j]
        ans0 = ans[j]
        for m in range(101):
            ans0 = max(ans0, dp0[m] - m * k)
        ans[j] = ans0
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph1(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        s[v + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def make_graph2(n, m):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = [s]
    visit = [0] * (n + 1)
    visit[s] = 1
    parent = [-1] * (n + 1)
    for i in q:
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if not visit[j]:
                q.append(j)
                visit[j] = 1
                parent[j] = i
    return (q, parent)

def f(u, v):
    return 201 * u + v
n = int(input())
(G, s0) = make_graph1(n, n - 1)
(p, parent) = bfs(1)
q = int(input())
(x, v0, k0) = ([0] * (2 * q), [0] * q, [0] * q)
for i in range(q):
    (v, k) = map(int, input().split())
    (x[2 * i], x[2 * i + 1]) = (k, i)
    (v0[i], k0[i]) = (v, k)
m = 200005
(Q1, s1) = make_graph2(m, q)
for i in range(q):
    x[2 * i] = v0[i]
(Q2, s2) = make_graph2(n, q)
p = p[::-1]
ans = [0] * q
for k in range(1000):
    if s1[k] == s1[k + 1]:
        continue
    dp = [0] * (n + 1)
    for i in p[:-1]:
        dp[parent[i]] += max(1, dp[i] - k)
    for w in range(s1[k], s1[k + 1]):
        i = Q1[w]
        v = v0[i]
        ans[i] = dp[v]
dp = [0] * (201 * (n + 1))
cnt = [1] * (n + 1)
for i in p:
    dp0 = [0] * 201
    for v in range(s0[i], s0[i + 1]):
        j = G[v]
        if parent[i] == j:
            continue
        dp1 = [k + 1 for k in dp0]
        for k in range(min(cnt[j], 200)):
            dpk = dp[f(j, k)]
            for l in range(min(cnt[i], 200 - k)):
                dp1[k + l + 1] = max(dp1[k + l + 1], dpk + dp0[l])
        cnt[i] += cnt[j]
        dp0 = dp1
    j = 201 * i
    for k in range(201):
        dp[j + k] = dp0[k]
    for w in range(s2[i], s2[i + 1]):
        j = Q2[w]
        k = k0[j]
        ans0 = ans[j]
        for m in range(201):
            ans0 = max(ans0, dp0[m] - m * k)
        ans[j] = ans0
sys.stdout.write('\n'.join(map(str, ans)))