A Growing Tree (Codeforces 1891F)
Tags: Others, trees

You are given a rooted tree with the root at vertex $$$1$$$, initially consisting of a single vertex. Each vertex has a numerical value, initially set to $$$0$$$. There are also $$$q$$$ queries of two types:   The first type: add a child vertex with the number $$$sz + 1$$$ to vertex $$$v$$$, where $$$sz$$$ is the current size of the tree. The numerical value of the new vertex will be $$$0$$$.  The second type: add $$$x$$$ to the numerical values of all vertices in the subtree of vertex $$$v$$$. After all queries, output the numerical value of all of the vertices in the final tree.

Input: The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) — the number of test cases. The descriptions of the test cases follow.The first line of each test case contains a single integer $$$q$$$ ($$$1 \leq q \leq 5 \cdot 10^5$$$) — the number of queries.The following $$$q$$$ lines can fall into two cases:   The first type of query: The $$$i$$$-th line contains two integers $$$t_i$$$ ($$$t_i = 1$$$), $$$v_i$$$. You need to add a child with the number $$$sz + 1$$$ to vertex $$$v_i$$$, where $$$sz$$$ is the current size of the tree. It is guaranteed that $$$1 \leq v_i \leq sz$$$.  The second type of query: The $$$i$$$-th line contains three integers $$$t_i$$$ ($$$t_i = 2$$$), $$$v_i$$$, $$$x_i$$$ ($$$-10^9 \leq x_i \leq 10^9$$$). You need to add $$$x_i$$$ to all numerical values of vertices in the subtree of $$$v_i$$$. It is guaranteed that $$$1 \leq v_i \leq sz$$$, where $$$sz$$$ is the current size of the tree. It is guaranteed that the sum of $$$q$$$ across all test cases does not exceed $$$5 \cdot 10^5$$$.

Output: For each test case, output the numerical value of each vertex of the final tree after all queries have been performed.

Note: In the first case, the final tree with the assigned numerical values will look like this:   The final tree with the assigned numerical values 

Sample Inputs:
3
9
2 1 3
1 1
2 2 1
1 1
2 3 2
1 3
2 1 4
1 3
2 3 2
5
2 1 1
1 1
2 1 -1
1 1
2 1 1
5
1 1
1 1
2 1 1
2 1 3
2 2 10

Sample Outputs:
7 5 8 6 2 
1 0 1 
4 14 4

Solution (Python):
""""""
from io import BytesIO, IOBase
import os
import sys
BUFSIZE = 64

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))

def input():
    return sys.stdin.readline().rstrip('\r\n')

def solve():
    q = int(input())
    fenwick = [0] * (q + 10)

    def lowbit(x):
        return x & -x

    def update(index, d):
        while index <= q:
            fenwick[index] += d
            index += lowbit(index)

    def getsum(index):
        res = 0
        while index > 0:
            res += fenwick[index]
            index -= lowbit(index)
        return res
    size = 1
    tree = [[] for _ in range(q + 10)]
    node_create = [-1] * (q + 10)
    node_create[1] = 0
    tree_ops = [[] for _ in range(q + 10)]
    parents = [-1 for _ in range(q + 10)]
    for q_idx in range(1, q + 1):
        query = list(map(int, input().strip().split()))
        if query[0] == 1:
            size += 1
            cur_node = query[1]
            node_create[size] = q_idx
            tree[cur_node].append(size)
            parents[size] = cur_node
        elif query[0] == 2:
            (cur_node, val) = query[1:]
            tree_ops[cur_node].append((val, q_idx))
    res = [0] * (size + 1)
    stack = []
    stack.append((1, 0))
    while stack:
        (root, state) = stack.pop()
        if state == 0:
            for (val, q_idx) in tree_ops[root]:
                update(q_idx, val)
            res[root] = getsum(q) - getsum(node_create[root])
            stack.append((root, 1))
            for nxt_node in tree[root]:
                stack.append((nxt_node, 0))
        if state == 1:
            for (val, q_idx) in tree_ops[root]:
                update(q_idx, -val)
    print(*res[1:])
    return
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    solve()

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

def f(u, v):
    return u * z0 + v

def make_graph(n, m, x):
    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 fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
t = int(input())
ans = []
z0 = pow(10, 6)
for _ in range(t):
    q = int(input())
    (x, y) = ([], [])
    n = 1
    for _ in range(q):
        t0 = list(map(int, input().split()))
        if t0[0] == 1:
            v = t0[1]
            n += 1
            x.append(v)
            x.append(n)
        else:
            (v, z) = (t0[1], t0[2])
            y.append(v)
            y.append(f(z, n))
    (G, s0) = make_graph(n, n - 1, x)
    (H, s1) = make_graph(n, len(y) >> 1, y)
    tree = fenwick_tree(n + 1)
    s = 0
    for v in range(s1[1], s1[2]):
        (x, i) = divmod(H[v], z0)
        add(i, x)
        s += x
    st = [1]
    ans0 = [0] * n
    now = list(s0)
    while st:
        i = st[-1]
        if now[i] ^ s0[i + 1]:
            j = G[now[i]]
            now[i] += 1
            for v in range(s1[j], s1[j + 1]):
                (x, k) = divmod(H[v], z0)
                add(k, x)
                s += x
            st.append(j)
        else:
            j = st.pop()
            ans0[j - 1] = s - get_sum(j - 1)
            for v in range(s1[j], s1[j + 1]):
                (x, k) = divmod(H[v], z0)
                add(k, -x)
                s -= x
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))

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

def f(u, v):
    return u * z0 + v

def make_graph(n, m, x):
    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 fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
t = int(input())
ans = []
z0 = pow(10, 6)
for _ in range(t):
    q = int(input())
    (x, y) = ([], [])
    n = 1
    for _ in range(q):
        t0 = list(map(int, input().split()))
        if t0[0] == 1:
            v = t0[1]
            n += 1
            x.append(v)
            x.append(n)
        else:
            (v, z) = (t0[1], t0[2])
            y.append(v)
            y.append(f(z, n))
    (G, s0) = make_graph(n, n - 1, x)
    (H, s1) = make_graph(n, len(y) >> 1, y)
    tree = fenwick_tree(n + 1)
    s = 0
    for v in range(s1[1], s1[2]):
        (x, i) = divmod(H[v], z0)
        add(i, x)
        s += x
    st = [1]
    ans0 = [0] * n
    now = list(s0)
    while st:
        i = st[-1]
        if now[i] ^ s0[i + 1]:
            j = G[now[i]]
            now[i] += 1
            for v in range(s1[j], s1[j + 1]):
                (x, k) = divmod(H[v], z0)
                add(k, x)
                s += x
            st.append(j)
        else:
            j = st.pop()
            ans0[j - 1] = s - get_sum(j - 1)
            for v in range(s1[j], s1[j + 1]):
                (x, k) = divmod(H[v], z0)
                add(k, -x)
                s -= x
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))