You are given a tree consisting of n nodes and rooted at 1. Each node and each edge of the tree have a value associated with them. Consider a node j and one of it's ancestor node i. Cost of node j with respect to node i is defined as sum of value of node j and sum of value of all edges present in the simple path from node i to node j. For each node i, output the number of distinct costs of all its descendants.
Input Format
First line contains n denoting the number of tree nodes.
Next n-1 lines each contain 3 integer numbers a,b,c denoting an edge between node a and node b of value c.
Next line contains n integers denoting the value of each node.
Output Format
For node i ranging from 1 to n, output the number of distinct costs among its descendants, each on a new line.
Constraints
1≤n≤105
−109≤ValueOfNode,ValueOfEdge≤109
For node 1:
Cost of node 1: 0 - 1 = -1
Cost of node 2: 1 - 4 = -3
Cost of node 3: 2 + 5 = 7
Cost of node 4:2 - 1 + 6 = 7
Number of distinct costs : 3
For node 2:
Cost of node 2: 0 - 4 = -4
Number of distinct costs : 1
For node 3:
Cost of node 3: 0 + 5 = 5
Cost of node 4: -1 + 6 = 5
Number of distinct costs : 1
For node 4:
Cost of node 4: 0 + 6 = 6
Number of distinct costs : 1
