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: Accepted

Solution code:
import sys
 
sys.setrecursionlimit(int(1e6))
 
 
class B_I_T:
    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 = B_I_T(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:
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:
from collections import deque

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
write = sys.stdout.write
N = int(readline())
G = [None]*N
for i in range(N):
    k, *c = map(int, readline().split())
    G[i] = c

H = [0]*N
prv = [None]*N
def dfs(v):
    s = 1; heavy = None; m = 0
    for w in G[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s
dfs(0)


SS = []
D = []
L = [0]*N
I = [0]*N
que = deque([(0, 0)])
while que:
    v, d = que.popleft()
    S = []
    k = len(SS)
    while v is not None:
        I[v] = len(S)
        S.append(v)
        L[v] = k
        h = H[v]
        for w in G[v]:
            if h == w:
                continue
            que.append((w, d+1))
        v = h
    SS.append(S)
    D.append(d)


C = list(map(len, SS))
DS = [[0]*(c+1) for c in C]
def add(K, data, k, x):
    while k <= K:
        data[k] += x
        k += k & -k
def get(K, data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s

def query_add(v, x):
    l = L[v]
    add(C[l], DS[l], I[v]+1, x)
    v = prv[SS[l][0]]

def query_sum(v):
    s = 0
    while v is not None:
        l = L[v]
        s += get(C[l], DS[l], I[v]+1)
        v = prv[SS[l][0]]
    return s


Q = int(readline())
ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        ans.append(str(query_sum(cmd[0])))
    else:
        v, w = cmd
        query_add(v, w)
write("\n".join(ans))
write("\n")

Submission status: Runtime Error

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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
G = [None for i in range(N)]
for i in range(N):
  temp = list(map(int, input().split()))
  G[i] = temp[1:]
  
INF = 2**31 -1

temp = 1
while temp < N:
  temp *= 2

lis = [INF for i in range(2*temp-1)]

def getSum(x):
  x += temp-1
  w_sum = lis[x]
  while x > 0:
    x = (x-1) // 2
    w_sum += lis[x]
  return w_sum

def add(a, b, x, k=0, l=0, r=temp):
  if r <= a or b <= l:
    return 0

  if a <= l and r <= b:
    lis[k] += x
    return 0
  
  add(a, b, k*2+1, l, (l+r)//2)
  add(a, b, k*2+2, (l+r)//2, r)
arr = [[0,0] for i in range(200010)]

def dfs(k, a=0):
  arr[0][k] = a
  a += 1
  for i in range(len(G[k])):
    dfs(G[k][i])
  arr[1][k] = a
  
dfs()
Q = int(intput())
for i in range(Q):
  querry = list(map(int, input().split()))
  if querry[0] == 0:
    add()
  else:
    print(getSum()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
G = [None for i in range(N)]
for i in range(N):
  temp = list(map(int, input().split()))
  G[i] = temp[1:]
  
INF = 2**31 -1

temp = 1
while temp < N:
  temp *= 2

lis = [INF for i in range(2*temp-1)]

def getSum(x):
  x += temp-1
  w_sum = lis[x]
  while x > 0:
    x = (x-1) // 2
    w_sum += lis[x]
  return w_sum

def add(a, b, x, k=0, l=0, r=temp):
  if r <= a or b <= l:
    return 0

  if a <= l and r <= b:
    lis[k] += x
    return 0
  
  add(a, b, k*2+1, l, (l+r)//2)
  add(a, b, k*2+2, (l+r)//2, r)

def dfs(k, a=0):
  arr[0][k] = a
  a += 1
  for i in range(len(G[k])):
    dfs(G[k][i])
  arr[1][k] = a
  
arr = [[0,0] for i in range(200010)]


  
dfs()
Q = int(input())
for i in range(Q):
  querry = list(map(int, input().split()))
  if querry[0] == 0:
    add(arr[0][querry[1]], arr[1][querry[1]],w)
  else:
    print(getSum(arr[0][querry[1]])

Submission status: Runtime Error

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(right[alist[1]], -alist[2])
    else:
        print(Object.getSum(right[alist[1]] - 1))