Kevin Needs Help

View as PDF

Submit solution

Points: 20
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kevin is planning something and needs your help, Kevin needs your help to check if two paths on a weighted tree are identical.

For two paths to be identical, the edges in which the two paths travel in are equal. In other words, given two paths (say one from u to v and one from n to m) the weight of the i^{th} edge of the first path is equal to the weight of the i^{th} edge of the second path. Both paths must have the same number of edges to be identical

If two paths are identical, print T, else print F.

Input Specification

The first line will contain N and Q (1 \le N,Q \le 10^5), the number of nodes in the weighted tree and the number of queries.

The next N-1 lines will contain u, v, and w (1 \le u, v \le N, 1 \le w \le 100), a bidirectional edge from node u to v of weight w.

The next Q lines will contain u, v, n, and m (1 \le u,v,n,m \le N), Kevin asking if path u to v is identical to path n to m.

Output Specification

Print Q lines, the answer to each query.

Sample Input 1

10 5
1 2 1
2 3 2
3 4 3
4 5 4
3 6 5
7 3 2
8 3 3
9 7 1
8 10 4
9 5 1 10
9 10 1 5
10 9 5 1
7 8 2 4
10 9 1 5

Sample Output 1

T
T
T
T
F

Comments

There are no comments at the moment.