SOLVE

LATER

Gaurav and Unique Edges

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

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

Initializing Code Editor...

{"403b5d4": "/pagelets/recommended-problems/algorithm/gaurav-and-unique-edge/", "403b5bf": "/pagelets/problems-hint/algorithm/gaurav-and-unique-edge/", "403b592": "/pagelets/suggested-problems/algorithm/gaurav-and-unique-edge/", "403b56c": "/pagelets/show-submission/algorithm/gaurav-and-unique-edge/", "403b5a9": "/pagelets/problem-author-tester/algorithm/gaurav-and-unique-edge/"}

{}

realtime.hackerearth.com

80

9fc21480d91a9f9cd6aa5270df0f656b8b41ba95

58a29e5cae2309f04b28

/realtime/pusher/auth/