Little Girl and Problem on Trees (Codeforces 276E)
Tags: Others, trees

A little girl loves problems on trees very much. Here's one of them.A tree is an undirected connected graph, not containing cycles. The degree of node x in the tree is the number of nodes y of the tree, such that each of them is connected with node x by some edge of the tree. Let's consider a tree that consists of n nodes. We'll consider the tree's nodes indexed from 1 to n. The cosidered tree has the following property: each node except for node number 1 has the degree of at most 2.Initially, each node of the tree contains number 0. Your task is to quickly process the requests of two types:  Request of form: 0 v x d. In reply to the request you should add x to all numbers that are written in the nodes that are located at the distance of at most d from node v. The distance between two nodes is the number of edges on the shortest path between them.  Request of form: 1 v. In reply to the request you should print the current number that is written in node v. 

Input: The first line contains integers n (2 ≤ n ≤ 105) and q (1 ≤ q ≤ 105) — the number of tree nodes and the number of requests, correspondingly.Each of the next n  -  1 lines contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that show that there is an edge between nodes ui and vi. Each edge's description occurs in the input exactly once. It is guaranteed that the given graph is a tree that has the property that is described in the statement.Next q lines describe the requests.  The request to add has the following format: 0 v x d (1 ≤ v ≤ n, 1 ≤ x ≤ 104, 1 ≤ d < n).  The request to print the node value has the following format: 1 v (1 ≤ v ≤ n). The numbers in the lines are separated by single spaces.

Output: For each request to print the node value print an integer — the reply to the request.


Sample Inputs:
3 6
1 2
1 3
0 3 1 2
0 2 3 1
0 1 5 2
1 1
1 2
1 3

6 11
1 2
2 5
5 4
1 6
1 3
0 3 1 3
0 3 4 5
0 2 1 4
0 1 5 5
0 4 6 2
1 1
1 2
1 3
1 4
1 5
1 6

Sample Outputs:
9
9
6

11
17
11
16
17
11

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

class Dual_Segment_Tree:

    def __init__(self, N, f_act, e_act, operate, lst):
        self.N = N
        self.f_act = f_act
        self.e_act = e_act
        self.operate = operate
        self.lst = [None] * self.N
        for (i, x) in enumerate(lst):
            self.lst[i] = x
        self.segment_tree_act = [self.e_act] * (self.N + self.N)

    def __getitem__(self, i):
        if type(i) is int:
            if -self.N <= i < 0:
                i += self.N * 2
            elif 0 <= i < self.N:
                i += self.N
            else:
                raise IndexError('list index out of range')
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None or a < -self.N:
                a = 0
            elif self.N <= a:
                a = self.N
            elif a < 0:
                a += self.N
            if b == None or self.N <= b:
                b = self.N
            elif b < -self.N:
                b = 0
            elif b < 0:
                b += self.N
            return self.lst[slice(a, b, c)]

    def Operate_At(self, i):
        return self.operate(self.lst[i - self.N], self.segment_tree_act[i])

    def Propagate_At(self, i):
        self.segment_tree_act[i << 1] = self.f_act(self.segment_tree_act[i << 1], self.segment_tree_act[i])
        self.segment_tree_act[i << 1 | 1] = self.f_act(self.segment_tree_act[i << 1 | 1], self.segment_tree_act[i])
        self.segment_tree_act[i] = self.e_act

    def Propagate_Above(self, i):
        H = i.bit_length() - 1
        for h in range(H, 0, -1):
            self.Propagate_At(i >> h)

    def Operate_Range(self, a, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L < R:
            if L & 1:
                self.segment_tree_act[L] = self.f_act(self.segment_tree_act[L], a)
                L += 1
            if R & 1:
                R -= 1
                self.segment_tree_act[R] = self.f_act(self.segment_tree_act[R], a)
            L >>= 1
            R >>= 1

    def Update(self):
        for i in range(1, self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i] = self.e_act

    def __str__(self):
        import copy
        segment_tree_act = copy.deepcopy(self.segment_tree_act)
        for i in range(1, self.N):
            segment_tree_act[i << 1] = self.f_act(segment_tree_act[i << 1], segment_tree_act[i])
            segment_tree_act[i << 1 | 1] = self.f_act(segment_tree_act[i << 1 | 1], segment_tree_act[i])
            segment_tree_act[i] = self.e_act
            segment_tree_act[i] = self.e_act
        return '[' + ', '.join(map(str, [self.operate(x, a) for (x, a) in zip(self.lst, segment_tree_act[self.N:])])) + ']'
(N, Q) = map(int, readline().split())
graph = [[] for i 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
seen[0] = True
sequ = []
for x in graph[0]:
    sequ.append([])
    while True:
        seen[x] = True
        sequ[-1].append(x)
        for y in graph[x]:
            if not seen[y]:
                x = y
                break
        else:
            break
IJ = [None] * N
for (i, lst) in enumerate(sequ):
    for (j, x) in enumerate(lst):
        IJ[x] = (i, j)
tour = [0]
for lst in sequ:
    tour += lst
idx = [None] * N
for i in range(N):
    idx[tour[i]] = i
DST = Dual_Segment_Tree(N, lambda a, b: a + b, 0, lambda x, a: x + a, [0] * N)
DST_depth = Dual_Segment_Tree(N + 1, lambda a, b: a + b, 0, lambda x, a: x + a, [0] * (N + 1))
for _ in range(Q):
    query = map(int, readline().split())
    if next(query) == 0:
        (v, x, d) = query
        v -= 1
        if v == 0:
            DST_depth.Operate_Range(x, 0, d + 1)
        else:
            (i, j) = IJ[v]
            if 0 <= j - d:
                a = idx[sequ[i][j - d]]
                b = idx[sequ[i][min(j + d, len(sequ[i]) - 1)]]
                DST.Operate_Range(x, a, b + 1)
            else:
                DST_depth.Operate_Range(x, 0, d - j)
                if d - j - 1 < len(sequ[i]):
                    a = idx[sequ[i][d - j - 1]]
                    b = idx[sequ[i][min(j + d, len(sequ[i]) - 1)]]
                    DST.Operate_Range(x, a, b + 1)
    else:
        v = next(query)
        v -= 1
        if v:
            (i, j) = IJ[v]
        else:
            j = -1
        ans = DST[idx[v]] + DST_depth[j + 1]
        print(ans)

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)

class BIT:
    """"""
    __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, left: int, right: int, val: int) -> None:
        self._add(left, val)
        self._add(right + 1, -val)

    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

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
            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()
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
bfn = [0] * (n + 1)
f = [-1] * (n + 1)
dep = hld.dep
que = deque()
que.append([1, -1])
bb = 1
while que:
    (u, fa) = que.popleft()
    f[dep[u]] = max(f[dep[u]], bb)
    bfn[u] = bb
    bb += 1
    for v in g[u]:
        if v == fa:
            continue
        que.append([v, u])
b1 = BIT(n + 10)
b2 = BIT(n + 10)
for _ in range(q):
    op = li()
    if op[0] == 0:
        (u, x, d) = op[1:]
        if u == 1:
            if f[d + 1] == -1:
                b2.add(1, n + 5, x)
            else:
                b2.add(1, f[d + 1], x)
        elif dep[u] - dep[1] > d:
            b1.add(dfn[u] - d, min(dfn[u] + d, dfn[u] + size[u] - 1), x)
        elif dep[u] - dep[1] == d:
            b1.add(dfn[u] - d + 1, min(dfn[u] + d, dfn[u] + size[u] - 1), x)
            b1.add(1, 1, x)
        else:
            nd = d - (dep[u] - dep[1]) + 1
            if f[nd] == -1:
                b2.add(1, n + 5, x)
            else:
                b2.add(1, f[nd], x)
            if nd >= dep[u]:
                b1.add(dfn[u] - (dep[u] - 2), min(dfn[u] + (nd - dep[u]), dfn[u] + size[u] - 1), -x)
            else:
                b1.add(dfn[u] - (dep[u] - 2), min(dfn[u] - (dep[u] - nd), dfn[u] + size[u] - 1), -x)
            b1.add(dfn[u] - (dep[u] - 2), min(dfn[u] + d, dfn[u] + size[u] - 1), x)
    else:
        v = op[1]
        print(b1.query(dfn[v]) + b2.query(bfn[v]))

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

class Dual_Segment_Tree:

    def __init__(self, N, f_act, e_act, operate, lst):
        self.N = N
        self.f_act = f_act
        self.e_act = e_act
        self.operate = operate
        self.lst = [None] * self.N
        for (i, x) in enumerate(lst):
            self.lst[i] = x
        self.segment_tree_act = [self.e_act] * (self.N + self.N)

    def __getitem__(self, i):
        if type(i) is int:
            if -self.N <= i < 0:
                i += self.N * 2
            elif 0 <= i < self.N:
                i += self.N
            else:
                raise IndexError('list index out of range')
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None or a < -self.N:
                a = 0
            elif self.N <= a:
                a = self.N
            elif a < 0:
                a += self.N
            if b == None or self.N <= b:
                b = self.N
            elif b < -self.N:
                b = 0
            elif b < 0:
                b += self.N
            return self.lst[slice(a, b, c)]

    def Operate_At(self, i):
        return self.operate(self.lst[i - self.N], self.segment_tree_act[i])

    def Propagate_At(self, i):
        self.segment_tree_act[i << 1] = self.f_act(self.segment_tree_act[i << 1], self.segment_tree_act[i])
        self.segment_tree_act[i << 1 | 1] = self.f_act(self.segment_tree_act[i << 1 | 1], self.segment_tree_act[i])
        self.segment_tree_act[i] = self.e_act

    def Propagate_Above(self, i):
        H = i.bit_length() - 1
        for h in range(H, 0, -1):
            self.Propagate_At(i >> h)

    def Operate_Range(self, a, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L < R:
            if L & 1:
                self.segment_tree_act[L] = self.f_act(self.segment_tree_act[L], a)
                L += 1
            if R & 1:
                R -= 1
                self.segment_tree_act[R] = self.f_act(self.segment_tree_act[R], a)
            L >>= 1
            R >>= 1

    def Update(self):
        for i in range(1, self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i] = self.e_act

    def __str__(self):
        import copy
        segment_tree_act = copy.deepcopy(self.segment_tree_act)
        for i in range(1, self.N):
            segment_tree_act[i << 1] = self.f_act(segment_tree_act[i << 1], segment_tree_act[i])
            segment_tree_act[i << 1 | 1] = self.f_act(segment_tree_act[i << 1 | 1], segment_tree_act[i])
            segment_tree_act[i] = self.e_act
            segment_tree_act[i] = self.e_act
        return '[' + ', '.join(map(str, [self.operate(x, a) for (x, a) in zip(self.lst, segment_tree_act[self.N:])])) + ']'
(N, Q) = map(int, readline().split())
graph = [[] for i 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
seen[0] = True
sequ = []
for x in graph[0]:
    sequ.append([])
    while True:
        seen[x] = True
        sequ[-1].append(x)
        for y in graph[x]:
            if not seen[y]:
                x = y
                break
        else:
            break
IJ = [None] * N
for (i, lst) in enumerate(sequ):
    for (j, x) in enumerate(lst):
        IJ[x] = (i, j)
tour = [0]
for lst in sequ:
    tour += lst
idx = [None] * N
for i in range(N):
    idx[tour[i]] = i
DST = Dual_Segment_Tree(N, lambda a, b: a + b, 0, lambda x, a: x + a, [0] * N)
DST_depth = Dual_Segment_Tree(N + 1, lambda a, b: a + b, 0, lambda x, a: x + a, [0] * (N + 1))
for _ in range(Q):
    query = map(int, readline().split())
    if next(query) == 0:
        (v, x, d) = query
        v -= 1
        if v == 0:
            DST_depth.Operate_Range(x, 0, d + 1)
        else:
            (i, j) = IJ[v]
            if 0 <= j - d:
                a = idx[sequ[i][j - d]]
                b = idx[sequ[i][min(j + d, len(sequ[i]) - 1)]]
                DST.Operate_Range(x, a, b + 1)
            else:
                DST_depth.Operate_Range(x, 0, d - j)
                if d - j - 1 < len(sequ[i]):
                    a = idx[sequ[i][d - j - 1]]
                    b = idx[sequ[i][min(j + d, len(sequ[i]) - 1)]]
                    DST.Operate_Range(x, a, b + 1)
    else:
        v = next(query)
        v -= 1
        if v:
            (i, j) = IJ[v]
        else:
            j = -1
        ans = DST[idx[v]] + DST_depth[j + 1]
        print(ans)