Partial Sum (or difference array technique) on Tree

Problem Statement

Partial Sum on a Tree Problem Description You are given a tree with n nodes numbered 1 to n , rooted at node 1 . Node i starts with an initial value values[i-1] . You must process q queries. Each query is a triple type x y and is one of two kinds. Type 1 - 1 x y : add y to every node in the subtree rooted at node x (node x included). Type 2 - 2 x y : add y to every node that is not in the subtree rooted at node x . After all q queries have been applied, report the final value of every node. The subtree of x is x together with all nodes whose path to the root passes through x . Input Format The first line contains the integer n . The next n integers are the initial values of nodes 1, 2, ..., n . The next n - 1 lines each contain two integers u v , an undirected edge of the tree. When n is 1 there are no edge lines. The next integer is q . Each of the next q lines contains three integers type x y . Output Format Print n integers on a single line, separated by single spaces: the final val