CF276E Little Girl and Problem on 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 $ .

N/A

N/A