Ediameter
Practice
5 (2 votes)
Dynamic programming
Algorithms
Medium
Trees
Dynamic programming
Problem
47% Success 278 Attempts 30 Points 2s Time Limit 256MB Memory 1024 KB Max Code

You are provided a weighted tree that consists of \(n\) nodes. For each edge of the tree, print the number of diameters that is a part of an edge. Note:

  • Diameter is the longest path in the tree.
  • The edges are numbered in the same order as they are mentioned in the sample input.

Input format

The first line of the input consists of an integer \(n\) that is followed by \(n-1\) lines. Each line consists of three space-separated integers, \(a\), \(b\), and \(c\). These space-separated integers denote an edge between nodes \(a\) and \(b\) that weighs \(c\).

Output format

For each edge of the tree (in the order they are mentioned in the sample input), print the total number of diameters that is a part of an edge.

Constraints

\(1\leq n\leq 10^5\)

\(1\leq a,b\leq n\)

\(a\neq b\)

\(0\leq c\leq 10^9\)

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

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
3 votes
Tags:
TreeDynamic ProgrammingAlgorithmsMedium
Points:30
1 votes
Tags:
TreeDynamic ProgrammingAlgorithmsMedium
Points:30
10 votes
Tags:
Dynamic ProgrammingAlgorithmsTrees