Heaviest edge - MarisaOJ: Marisa Online Judge

You are given a weighted tree of

$n$ vertices rooted at

$1$ . There are

$q$ queries, each of the form

$(u, v)$ , find weight of the heaviest edge on the simple path between

$u$ and

$v$ . ### Input - The first line contain 2 integers

$n, q$ . - The next

$n - 1$ lines, each line contains 3 integers

$u, v, w$ , there is an edge of weight

$w$ between

$u$ and

$v$ . - The next

$q$ lines, each line contains 2 integers

$u, v$ , an query. ### Output - Print

$q$ integers, the answers to

$q$ queries. ### Constraints -

$1 \le n, q\le 10^5$ . -

$1 \le u, v \le n$ . -

$1 \le w \le 10^9$ . ### Example Input:

$7 3 1 2 1 1 3 2 2 4 3 2 5 2 3 6 1 3 7 3 4 5 2 6 2 1$

Output:

$3 2 1$

Lowest common ancestor (LCA)
	LCA
	Distance query
	Robot on tree
	Heaviest edge
	Equal path
	Triplet
	Path update
	Second best minimum spanning tree
	Oggy and the cockroaches

Topic

Graph

Tree

Rating

1500

Solution (0)

Solution