CF1076E Vasya and a Tree

Vasya has a tree consisting of $ n $ vertices with root in vertex $ 1 $ . At first all vertices has $ 0 $ written on it. Let $ d(i, j) $ be the distance between vertices $ i $ and $ j $ , i.e. number of edges in the shortest path from $ i $ to $ j $ . Also, let's denote $ k $ -subtree of vertex $ x $ — set of vertices $ y $ such that next two conditions are met: - $ x $ is the ancestor of $ y $ (each vertex is the ancestor of itself); - $ d(x, y) \le k $ . Vasya needs you to process $ m $ queries. The $ i $ -th query is a triple $ v_i $ , $ d_i $ and $ x_i $ . For each query Vasya adds value $ x_i $ to each vertex from $ d_i $ -subtree of $ v_i $ . Report to Vasya all values, written on vertices of the tree after processing all queries.

N/A

N/A

In the first exapmle initial values in vertices are $ 0, 0, 0, 0, 0 $ . After the first query values will be equal to $ 1, 1, 1, 0, 0 $ . After the second query values will be equal to $ 1, 11, 1, 0, 0 $ . After the third query values will be equal to $ 1, 11, 1, 100, 0 $ .