All Tracks Data Structures Trees Problem

Gaurav and Unique Edges
Tag(s):

Medium

Problem
Editorial
Analytics

Mr Gaurav is trying to solve one graph problem. The problem says, Given N nodes and N-1 edges connecting the nodes. There is a unique path between each pair of nodes. Each edge has some weight w. Q queries are given, for each query, find no of unique edge weights present in the path connecting u and v. Since Gaurav is President of CSS, he has got some urgent work. So, he asked you to solve the problem for him.

Input

First line of input contains a single integer N.

Next N-1 lines contains 3 space separated integer u, v, w representing an edge connecting u and v and having weight w.

Next line contains a single integer Q.

Next Q lines contains 2 space separated integer u and v.

Output

Print Q lines and each line should print one integer denoting the count of unique edges present in the path between u and v.

Constraints

2 ≤ N,Q ≤ 100 000

1 ≤ u,v ≤ 100 000

1 ≤ w ≤ 10

Setter : Sourav Kumar Paul

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

Query 1 : Edges are : (3,2) -1, (2,1) - 3, (1,5) - 2, (5,6) - 1

So, no of unique edges are 3.

Time Limit: 5.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: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications