Problem:

Range Query on a Tree

Write a program which manipulates a weighted rooted tree $T$ with the following operations:

  
$add(v,w)$: add $w$ to the edge which connects node $v$ and its parent

  
$getSum(u)$: report the sum of weights of all edges from the root to node $u$

  The given tree $T$ consists of $n$ nodes and every node has a unique ID from $0$ to $n-1$ respectively where ID of the root is $0$.
  Note that all weights are initialized to zero.

Input

  The input is given in the following format.

$n$

$node_0$

$node_1$

$node_2$

$:$

$node_{n-1}$

$q$

$query_1$

$query_2$

$:$

$query_{q}$

  The first line of the input includes an integer $n$, the number of nodes in the tree.

  In the next $n$ lines,the information of node $i$ is given in the following format:

ki c1 c2 ... ck

  $k_i$ is the number of children of node $i$, and $c_1$ $c_2$ ... $c_{k_i}$ are node IDs of 1st, ... $k$th child of node $i$.

  In the next line, the number of queries $q$ is given. In the next $q$ lines, $i$th query is given in the following format:

0 v w

or

1 u

  The first integer represents the type of queries.'0' denotes $add(v, w)$ and '1' denotes $getSum(u)$.

Constraints

  
All the inputs are given in integers

  
$ 2 \leq n \leq 100000 $

  
$ c_j < c_{j+1} $   $( 1 \leq j \leq k-1 )$

  
$ 2 \leq q \leq 200000 $

  
$ 1 \leq u,v \leq n-1 $

  
$ 1 \leq w \leq 10000 $

Output

  For each $getSum$ query, print the sum in a line.

Sample Input 1

6
2 1 2
2 3 5
0
0
0
1 4
7
1 1
0 3 10
1 2
0 4 20
1 3
0 5 40
1 4

Sample Output 1

0
0
10
60

Sample Input 2

4
1 1
1 2
1 3
0
6
0 3 1000
0 2 1000
0 1 1000
1 1
1 2
1 3

Sample Output 2

1000
2000
3000

Sample Input 3

2
1 1
0
4
0 1 1
1 1
0 1 1
1 1

Sample Output 3

1
2



Sample input:
6
2 1 2
2 3 5
0
0
0
1 4
7
1 1
0 3 10
1 2
0 4 20
1 3
0 5 40
1 4


Sample output:
0
0
10
60

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
class weightRtree:
    def __init__(self, num):
        self.num = num
        self.weight = (num+1)*[0] 
      
    def add(self, v, w):
        if v == 0:
            return 0
        while v <= self.num:
            self.weight[v] += w
            v += (-v&v)    

    def getSum(self, u):
        temp = 0
        while u > 0:
            temp += self.weight[u]
            u -= (-u&u)
        return temp

N = int(input())
left = [0]*N
right = [0]*N
Tree = [set(map(int, input().split()[1:])) for i in range(N)]

def DFS(count, source):
    count += 1
    left[source] = count
    for item in Tree[source]:
        count = DFS(count, item)
    count += 1
    right[source] = count
    return count

Object = weightRtree(DFS(1, 0))

Q = int(input())
for i in range(Q):
    alist = list(map(int, input().split()))
    if not alist[0]:
        Object.add(left[alist[1]], alist[2])
        Object.add(left[alist[1]], -alist[2])
    else:
        print(Object.getSum(right[alist[1]] - 1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
class weightRtree:
    def __init__(self, num):
        self.num = num
        self.weight = [0]*(num+1) 
      
    def add(self, v, w):
        if v == 0:
            return 0
        while v <= self.num:
            self.weight[v] += w
            v += (-v)&v    

    def getSum(self, u):
        temp = 0
        while u > 0:
            temp += self.weight[u]
            u -= (-u)&u
        return temp

N = int(input())
left = [0]*N
right = [0]*N
Tree = [set(map(int, input().split()[1:])) for i in range(N)]

def DFS(count, source):
    count += 1
    left[source] = count
    for item in Tree[source]:
        count = DFS(count, item)
    count += 1
    right[source] = count
    return count

Object = weightRtree(DFS(1, 0))

Q = int(input())
for i in range(Q):
    alist = list(map(int, input().split()))
    if not alist[0]:
        Object.add(left[alist[1]], alist[2])
        Object.add(left[alist[1]], -alist[2])
    else:
        print(Object.getSum(right[alist[1]] - 1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
class weightRtree:
    def __init__(self, num):
        self.num = num
        self.weight = [0] * (num+1) 
      
    def add(self, v, w):
        if v == 0:
            return 0
        while v <= self.num:
            self.weight[v] += w
            v += (-v) & v    

    def getSum(self, u):
        temp = 0
        while u > 0:
            temp += self.weight[u]
            u -= (-u) & u
        return temp

N = int(input())
left = [0] * N
right = [0] * N
Tree = [set(map(int, input().split()[1:])) for i in range(N)]

def DFS(count, source):
    count += 1
    left[source] = count
    for item in Tree[source]:
        count = DFS(count, item)
    count += 1
    right[source] = count
    return count

Object = weightRtree(DFS(1, 0))

Q = int(input())
for i in range(Q):
    alist = list(map(int, input().split()))
    if not alist[0]:
        Object.add(left[alist[1]], alist[2])
        Object.add(left[alist[1]], -alist[2])
    else:
        print(Object.getSum(right[alist[1]] - 1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# GRL_5_D: Tree - Range Query on Tree


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class RAQ:
    """Segment Tree
    """
    def __init__(self, n, initial=0):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [initial] * self.size

    def add(self, i, j, v):
        def _add(r, lo, hi):
            if hi < i or lo > j:
                return
            elif i <= lo and hi <= j:
                self.data[r] += v
            else:
                mid = lo + (hi - lo)//2
                _add(r*2 + 1, lo, mid)
                _add(r*2 + 2, mid+1, hi)

        return _add(0, 0, self.size//2)

    def get(self, i):
        def _get(r, lo, hi, v):
            v += self.data[r]
            if lo == hi:
                return v
            mid = lo + (hi - lo)//2
            if mid >= i:
                return _get(r*2 + 1, lo, mid, v)
            else:
                return _get(r*2 + 2, mid+1, hi, v)

        return _get(0, 0, self.size//2, 0)


class PathSum:
    def __init__(self, graph, root):
        self.seg = RAQ(graph.v * 2)
        self._in = [0] * graph.v
        self._out = [0] * graph.v
        self.dfs(graph, root)

    def dfs(self, graph, root):
        visited = [False] * graph.v
        stack = [root]
        i = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                self._in[v] = i
                i += 1
                stack.append(v)
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        stack.append(w)
            else:
                self._out[v] = i
                i += 1

    def add(self, v, val):
        i = self._in[v]
        j = self._out[v]
        self.seg.add(i, j, val)

    def get(self, v):
        return self.seg.get(self._in[v])


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    raq = PathSum(g, 0)
    q = int(input())
    for _ in range(q):
        com, *args = [int(i) for i in input().split()]
        if com == 0:
            u, val = args
            raq.add(u, val)
        elif com == 1:
            u, = args
            print(raq.get(u))
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# GRL_5_D: Tree - Range Query on Tree
# Eular Tour Technique
# DFSの結果でサブツリーの範囲がわかるので、range add queryを利用して
# add/getを行う


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class RAQ:
    """Segment Tree
    """
    def __init__(self, n, initial=0):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [initial] * self.size

    def add(self, i, j, v):
        def _add(r, lo, hi):
            if hi < i or lo > j:
                return
            elif i <= lo and hi <= j:
                self.data[r] += v
            else:
                mid = lo + (hi - lo)//2
                _add(r*2 + 1, lo, mid)
                _add(r*2 + 2, mid+1, hi)

        return _add(0, 0, self.size//2)

    def get(self, i):
        def _get(r, lo, hi, v):
            v += self.data[r]
            if lo == hi:
                return v
            mid = lo + (hi - lo)//2
            if mid >= i:
                return _get(r*2 + 1, lo, mid, v)
            else:
                return _get(r*2 + 2, mid+1, hi, v)

        return _get(0, 0, self.size//2, 0)


class PathSum:
    def __init__(self, graph, root):
        self.seg = RAQ(graph.v)
        self._in = [0] * graph.v
        self._out = [0] * graph.v
        self.dfs(graph, root)

    def dfs(self, graph, root):
        visited = [False] * graph.v
        stack = [root]
        i = 0
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                self._in[v] = i
                i += 1
                stack.append(v)
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        stack.append(w)
            else:
                self._out[v] = i - 1

    def add(self, v, val):
        i = self._in[v]
        j = self._out[v]
        self.seg.add(i, j, val)

    def get(self, v):
        return self.seg.get(self._in[v])


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    raq = PathSum(g, 0)
    q = int(input())
    for _ in range(q):
        com, *args = [int(i) for i in input().split()]
        if com == 0:
            u, val = args
            raq.add(u, val)
        elif com == 1:
            u, = args
            print(raq.get(u))
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# GRL_5_D: Tree - Range Query on Tree


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class RAQ:
    """Segment Tree
    """
    def __init__(self, n, initial=0):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [initial] * self.size

    def add(self, i, j, v):
        def _add(r, lo, hi):
            if i <= lo and hi <= j:
                data[r] += v
            elif i <= hi and lo <= j:
                mid = lo + (hi - lo)//2
                _add(r*2 + 1, lo, mid)
                _add(r*2 + 2, mid+1, hi)

        data = self.data
        return _add(0, 0, self.size//2)

    def get(self, i):
        def _get(r, lo, hi, v):
            v += self.data[r]
            if lo == hi:
                return v
            mid = lo + (hi - lo)//2
            if mid >= i:
                return _get(r*2 + 1, lo, mid, v)
            else:
                return _get(r*2 + 2, mid+1, hi, v)

        return _get(0, 0, self.size//2, 0)


class PathSum:
    def __init__(self, graph, root):
        self.seg = RAQ(graph.v)
        self._dfs(graph, root)

    def _dfs(self, graph, root):
        visited = [False] * graph.v
        pos = [None] * graph.v
        stack = [root]
        n = 0
        ns = []
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                ns.append(n)
                n += 1
                stack.append(v)
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        stack.append(w)
            else:
                pos[v] = (ns.pop(), n - 1)

        self._pos = pos

    def add(self, v, val):
        i, j = self._pos[v]
        self.seg.add(i, j, val)

    def get(self, v):
        return self.seg.get(self._pos[v][0])


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    raq = PathSum(g, 0)
    q = int(input())
    for _ in range(q):
        com, *args = [int(i) for i in input().split()]
        if com == 0:
            u, val = args
            raq.add(u, val)
        elif com == 1:
            u, = args
            print(raq.get(u))
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
N = 10 ** 5
prt = [0] * (N + 1)
left = [-1] + [0] * N
right = [-1] + [0] * N
sz = [0] + [1] * N
key = [0] * (N + 1)
val = [0] * (N + 1)
rev = [0] * (N + 1)


def update(i, l, r):
    # assert 1 <= i <= N
    sz[i] = 1 + sz[l] + sz[r]
    val[i] = key[i] + val[l] + val[r]


def swap(i):
    if i:
        left[i], right[i] = right[i], left[i]
        rev[i] ^= 1


def prop(i):
    swap(left[i])
    swap(right[i])
    rev[i] = 0
    return 1


def splay(i):
    # assert 1 <= i <= N
    x = prt[i]
    rev[i] and prop(i)

    li = left[i];
    ri = right[i]
    while x and not left[x] != i != right[x]:
        y = prt[x]
        if not y or left[y] != x != right[y]:
            if rev[x] and prop(x):
                li, ri = ri, li
                swap(li);
                swap(ri)

            if left[x] == i:
                left[x] = ri
                prt[ri] = x
                update(x, ri, right[x])
                ri = x
            else:
                right[x] = li
                prt[li] = x
                update(x, left[x], li)
                li = x
            x = y
            break

        rev[y] and prop(y)
        if rev[x] and prop(x):
            li, ri = ri, li
            swap(li);
            swap(ri)

        z = prt[y]
        if left[y] == x:
            if left[x] == i:
                v = left[y] = right[x]
                prt[v] = y
                update(y, v, right[y])

                left[x] = ri;
                right[x] = y
                prt[ri] = x
                update(x, ri, y)

                prt[y] = ri = x
            else:
                left[y] = ri
                prt[ri] = y
                update(y, ri, right[y])

                right[x] = li
                prt[li] = x
                update(x, left[x], li)

                li = x;
                ri = y
        else:
            if right[x] == i:
                v = right[y] = left[x]
                prt[v] = y
                update(y, left[y], v)

                left[x] = y;
                right[x] = li
                prt[li] = x
                update(x, y, li)

                prt[y] = li = x
            else:
                right[y] = li
                prt[li] = y
                update(y, left[y], li)

                left[x] = ri
                prt[ri] = x
                update(x, ri, right[x])

                li = y;
                ri = x

        x = z
        if left[z] == y:
            left[z] = i
            update(z, i, right[z])
        elif right[z] == y:
            right[z] = i
            update(z, left[z], i)
        else:
            break

    update(i, li, ri)
    left[i] = li;
    right[i] = ri
    prt[li] = prt[ri] = i
    prt[i] = x

    rev[i] = prt[0] = 0


def expose(i):
    p = 0
    cur = i
    while cur:
        splay(cur)
        right[cur] = p
        update(cur, left[cur], p)
        p = cur
        cur = prt[cur]
    splay(i)
    return i


def cut(i):
    expose(i)
    p = left[i]
    left[i] = prt[p] = 0
    return p


def link(i, p):
    expose(i)
    expose(p)
    prt[i] = p
    right[p] = i


def evert(i):
    expose(i)
    swap(i)
    rev[i] and prop(i)


def query(v):
    r = expose(v + 1)
    return val[r]


def query_add(v, w):
    key[v + 1] += w
    expose(v + 1)


readline = open(0).readline
writelines = open(1, 'w').writelines

N = int(readline())
for i in range(N):
    k, *C = map(int, readline().split())
    # for c in C:
    #    link(c+1, i+1)
    if k:
        expose(i + 1)
        for c in C:
            expose(c + 1)
            prt[c + 1] = i + 1
        right[i + 1] = C[0] + 1

Q = int(readline())
ans = []
for q in range(Q):
    t, *args = map(int, readline().split())
    if t:
        ans.append("%d\n" % query(args[0]))
    else:
        query_add(*args)
writelines(ans)

Submission status: Accepted

Solution code:
N = 10**5
prt = [0]*(N+1)
left = [-1] + [0]*N
right = [-1] + [0]*N
sz = [0] + [1]*N
key = [0]*(N+1)
val = [0]*(N+1)
rev = [0]*(N+1)
 
def update(i, l, r):
    #assert 1 <= i <= N
    sz[i] = 1 + sz[l] + sz[r]
    val[i] = key[i] + val[l] + val[r]
 
def swap(i):
    if i:
        left[i], right[i] = right[i], left[i]
        rev[i] ^= 1
 
def prop(i):
    swap(left[i])
    swap(right[i])
    rev[i] = 0
    return 1
 
def splay(i):
    #assert 1 <= i <= N
    x = prt[i]
    rev[i] and prop(i)
 
    li = left[i]; ri = right[i]
    while x and not left[x] != i != right[x]:
        y = prt[x]
        if not y or left[y] != x != right[y]:
            if rev[x] and prop(x):
                li, ri = ri, li
                swap(li); swap(ri)
 
            if left[x] == i:
                left[x] = ri
                prt[ri] = x
                update(x, ri, right[x])
                ri = x
            else:
                right[x] = li
                prt[li] = x
                update(x, left[x], li)
                li = x
            x = y
            break
 
        rev[y] and prop(y)
        if rev[x] and prop(x):
            li, ri = ri, li
            swap(li); swap(ri)
 
        z = prt[y]
        if left[y] == x:
            if left[x] == i:
                v = left[y] = right[x]
                prt[v] = y
                update(y, v, right[y])
 
                left[x] = ri; right[x] = y
                prt[ri] = x
                update(x, ri, y)
 
                prt[y] = ri = x
            else:
                left[y] = ri
                prt[ri] = y
                update(y, ri, right[y])
 
                right[x] = li
                prt[li] = x
                update(x, left[x], li)
 
                li = x; ri = y
        else:
            if right[x] == i:
                v = right[y] = left[x]
                prt[v] = y
                update(y, left[y], v)
 
                left[x] = y; right[x] = li
                prt[li] = x
                update(x, y, li)
 
                prt[y] = li = x
            else:
                right[y] = li
                prt[li] = y
                update(y, left[y], li)
 
                left[x] = ri
                prt[ri] = x
                update(x, ri, right[x])
 
                li = y; ri = x
 
        x = z
        if left[z] == y:
            left[z] = i
            update(z, i, right[z])
        elif right[z] == y:
            right[z] = i
            update(z, left[z], i)
        else:
            break
 
    update(i, li, ri)
    left[i] = li; right[i] = ri
    prt[li] = prt[ri] = i
    prt[i] = x
 
    rev[i] = prt[0] = 0
 
def expose(i):
    p = 0
    cur = i
    while cur:
        splay(cur)
        right[cur] = p
        update(cur, left[cur], p)
        p = cur
        cur = prt[cur]
    splay(i)
    return i
 
def cut(i):
    expose(i)
    p = left[i]
    left[i] = prt[p] = 0
    return p
 
def link(i, p):
    expose(i)
    expose(p)
    prt[i] = p
    right[p] = i
 
def evert(i):
    expose(i)
    swap(i)
    rev[i] and prop(i)
 
def query(v):
    r = expose(v+1)
    return val[r]
 
def query_add(v, w):
    key[v+1] += w
    expose(v+1)
 
 
readline = open(0).readline
writelines = open(1, 'w').writelines
 
N = int(readline())
for i in range(N):
    k, *C = map(int, readline().split())
    #for c in C:
    #    link(c+1, i+1)
    if k:
        expose(i+1)
        for c in C:
            expose(c+1)
            prt[c+1] = i+1
        right[i+1] = C[0]+1
 
Q = int(readline())
ans = []
for q in range(Q):
    t, *args = map(int, readline().split())
    if t:
        ans.append("%d\n" % query(args[0]))
    else:
        query_add(*args)
writelines(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(int(1e6))


class BIT:
	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)

	def get_sum(self, i):
		ret = 0
		while i > 0:
			ret += self.data[i]
			i -= (i & -i)
		return ret

	def add(self, i, w):
		if i == 0:
			return
		while i <= self.n:
			self.data[i] += w
			i += (i & -i)

def dfs(u, cnt):
	cnt += 1
	l[u] = cnt
	for c in tree[u]:
		cnt = dfs(c, cnt)
	cnt += 1
	r[u] = cnt
	return cnt

n = int(input())
l, r = [0] * n, [0] * n
tree = [set(map(int, input().split()[1:])) for _ in range(n)]

bit = BIT(dfs(0, 1))

q = int(input())
for _ in range(q):
	line = list(map(int, input().split()))
	if line[0]:
		print(bit.get_sum(r[line[1]] - 1))
	else:
		bit.add(l[line[1]], line[2])
		bit.add(r[line[1]], -line[2])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

class weightRtree:
    def __init__(self, num):
        self.num = num
        self.weight = [0] * (num+1) 
      
    def add(self, v, w):
        if v == 0:
            return 0
        while v <= self.num:
            self.weight[v] += w
            v += (-v) & v    

    def getSum(self, u):
        temp = 0
        while u > 0:
            temp += self.weight[u]
            u -= (-u) & u
        return temp

N = int(input())
left = [0] * N
right = [0] * N
Tree = [set(map(int, input().split()[1:])) for i in range(N)]

def DFS(count, source):
    count += 1
    left[source] = count
    for item in Tree[source]:
        count = DFS(count, item)
    count += 1
    right[source] = count
    return count

Object = weightRtree(DFS(1, 0))

Q = int(input())
for i in range(Q):
    alist = list(map(int, input().split()))
    if not alist[0]:
        Object.add(left[alist[1]], alist[2])
        Object.add(right[alist[1]], -alist[2])
    else:
        print(Object.getSum(right[alist[1]] - 1))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


# The class of range query on a Tree
class RQT:
    # The initialization of node
    def __init__(self, num):
        self.num = num
        self.weight = [0] * (num + 1)

    # weight add operation
    def add(self, v, w):
        if v == 0:
            return 0
        while v <= self.num:
            self.weight[v] += w
            v += (-v) & v

    # weight sum operation
    def getSum(self, u):
        temp = 0
        while u > 0:
            temp += self.weight[u]
            u -= (-u) & u
        return temp


N = int(input())
left = [0] * N
right = [0] * N
# use set to construct the tree
Tree = [set(map(int, input().split()[1:])) for i in range(N)]

# use DFS to search the target node
def DFS(count, source):
    count += 1
    left[source] = count
    for item in Tree[source]:
        count = DFS(count, item)
    count += 1
    right[source] = count
    return count


Object = RQT(DFS(1, 0))

# read the operation code
Q = int(input())
for i in range(Q):
    alist = list(map(int, input().split()))
    if not alist[0]:
        Object.add(left[alist[1]], alist[2])
        Object.add(right[alist[1]], -alist[2])
    else:
        print(Object.getSum(right[alist[1]] - 1))

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def heavylight_decomposition(self):
        self.order = [None for _ in range(self.n)]
        self.head = [None for _ in range(self.n)]
        self.head[self.root] = self.root
        self.next = [None for _ in range(self.n)]
        stack = [self.root]
        order = 0
        while stack:
            node = stack.pop()
            self.order[node] = order
            order += 1
            maxsize = 0
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                if maxsize < self.size[adj]:
                    maxsize = self.size[adj]
                    self.next[node] = adj
            for adj in self.tree[node]:
                if self.parent[node] == adj or self.next[node] == adj:
                    continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[node] is not None:
                self.head[self.next[node]] = self.head[node]
                stack.append(self.next[node])

    def range_hld(self, u, v, edge=False):
        res = []
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                res.append((self.order[self.head[v]], self.order[v] + 1))
                v = self.parent[self.head[v]]
            else:
                res.append((self.order[u] + edge, self.order[v] + 1))
                return res

    def subtree_hld(self, u):
        return self.order[u], self.order[u] + self.size[u]

    def lca_hld(self, u, v):
        while True:
            if self.order[u] > self.order[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.parent[self.head[v]]
            else:
                return u

class SegmentTree():
    def __init__(self, arr, func=min, ie=2**63):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.tree[self.n + i] = arr[i]
        for i in range(1, self.n)[::-1]:
            self.tree[i] = func(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, idx, x):
        idx += self.n
        self.tree[idx] = x
        while idx:
            idx >>= 1
            self.tree[idx] = self.func(self.tree[2 * idx], self.tree[2 * idx + 1])

    def query(self, lt, rt):
        lt += self.n
        rt += self.n
        vl = vr = self.ie
        while rt - lt > 0:
            if lt & 1:
                vl = self.func(vl, self.tree[lt])
                lt += 1
            if rt & 1:
                rt -= 1
                vr = self.func(self.tree[rt], vr)
            lt >>= 1
            rt >>= 1
        return self.func(vl, vr)


import sys
input = sys.stdin.readline

from operator import add

N = int(input())
E = []

for i in range(N):
    k, *c = map(int, input().split())
    for j in range(k):
        E.append((i + 1, c[j] + 1))

t = Tree(N, E)
t.setroot(0)
t.heavylight_decomposition()

st = SegmentTree([0] * N, add, 0)

res = []

Q = int(input())

for _ in range(Q):
    q, *p = map(int, input().split())
    if q == 0:
        v, w = p
        st.set(t.order[v], st.query(t.order[v], t.order[v] + 1) + w)
    else:
        s = 0
        u, = p
        for lt, rt in t.range_hld(0, u, edge=True):
            s += st.query(lt, rt)
        res.append(s)

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)


class BIT(object):
    def __init__(self, n: int) -> None:
        self.n = n
        self.data = [0] * (n + 1)

    def get_sum(self, i: int) -> int:
        ret = 0
        while i > 0:
            ret += self.data[i]
            i -= (i & -i)
        return ret

    def add(self, i: int, w: int) -> None:
        if i == 0:
            return
        while i <= self.n:
            self.data[i] += w
            i += (i & -i)


def dfs(u: int, cnt: int) -> int:
    global left, right
    cnt += 1
    left[u] = cnt
    for c in tree[u]:
        cnt = dfs(c, cnt)
    cnt += 1
    right[u] = cnt
    return cnt


if __name__ == "__main__":
    n = int(input())
    left, right = [0] * n, [0] * n
    tree = []
    for _ in range(n):
        _, *children = map(lambda x: int(x), input().split())
        tree.append(set(children))

    bit = BIT(dfs(0, 1))

    q = int(input())
    for _ in range(q):
        query = list(map(lambda x: int(x), input().split()))
        if query[0]:
            print(bit.get_sum(right[query[1]] - 1))
        else:
            bit.add(left[query[1]], query[2])
            bit.add(right[query[1]], -query[2])