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\le n\le 10^5\)
\(-10^9\le Value Of Node,Value Of Edge\le 10^9\)
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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor