SP913 QTREE2 - Query on a tree II

You are given a tree (an undirected acyclic connected graph) with **N** nodes, and edges numbered 1, 2, 3...**N**-1. Each edge has an integer value assigned to it, representing its length. We will ask you to perfrom some instructions of the following form: - **DIST a b** : ask for the distance between node **a** and node **b** or - **KTH a b k** : ask for the **k**-th node on the path from node **a** to node **b** **Example:** **N** = 6 1 2 1 // edge connects node 1 and node 2 has cost 1 2 4 1 2 5 2 1 3 1 3 6 2 Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6 **DIST 4 6** : answer is 5 (1 + 1 + 1 + 2 = 5) **KTH 4 6 4** : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3)

N/A

N/A