18577번 - Intellectual Prefix Maxima 다국어

A tree is an undirected graph in which any two vertices are connected by exactly one path. You are given a weighted tree with \(n\) vertices, where \(w(i, j)\) is weight of an edge between vertices \(i\) and \(j\). Consider a simple path \(P = (u, s_1, \dots , s_{t−1}, v)\) from vertex \(u\) to vertex \(v\). Denote the sequence of weights of the edges on path \(P\) by \(a = (a_1, a_2, \dots , a_t)\), where \(a_1 = w(u, s_1), a_2 = w(s_1, s_2), \dots , a_t = w(s_{t−1}, v)\).

Let \(f(u, v) = \sum_{i=1}^{t}{\max_{j=1\dots i}{\{a_j\}}}\) be the sum of prefix maxima on \(a\). You are given \(q\) queries, each of them is described with two integers, \(u\) and \(v\). For each query, you need to compute \(f(u, v)\).

The first line contains two integers \(n\) and \(q\) (\(1 \le n \le 2 \cdot 10^5, 1 \le q \le 10^6\)) separated by a single space: the number of vertices in the tree and the number of queries.

Each of the next \(n − 1\) lines contains three integers, \(a_i\), \(b_i\), and \(c_i\) (\(1 \le a_i, b_i \le n, a_i \ne b_i, 1 \le c_i \le 10^9\)): the vertices connected by the \(i\)-th edge and its weight. It is guaranteed that the given edges form a tree.

Each of the next \(q\) lines contains two integers \(u_i\) and \(v_i\) (\(1 \le u_i, v_i \le n\)): the \(i\)-th query.

Print \(q\) lines, the \(i\)-th of them should contain a single integer: the answer to the \(i\)-th query.