All Tracks Algorithms Dynamic Programming Problem

Shubham and Tree-1
Tag(s):

Algorithms, Dynamic Programming, Medium, Trees, medium

Problem
Editorial
Analytics

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\)

SAMPLE INPUT
4
1 2 1
1 3 2
3 4 -1
-1 -4 5 6
SAMPLE OUTPUT
3
1
1
1
Explanation

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

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

January Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?