Sum of Pairwise Distances on a Labeled Tree

You are given an unrooted tree with n nodes and weighted edges. Each node is assigned a unique label forming a permutation of the numbers \(1,2,\dots,n\). There are exactly \(n-1\) edges in the tree. You are also given \(m\) queries. Each query consists of two integers \(l\) and \(r\). For each query, consider the set of nodes whose labels lie in the interval \([l, r]\). For every pair of distinct nodes \((i,j)\) (with \(i < j\) based on their label values) in this set, compute the distance between them. The distance between any two nodes is defined as the sum of the weights of the edges on the unique simple path connecting them. Your task is to output the sum of distances for all such pairs for each query.

Note: The distance between a node and itself is 0.

Mathematical Formulation:
Given a tree \(T\) with nodes labeled by a permutation \(p_1, p_2, \dots, p_n\) of \(\{1,2,\ldots,n\}\) and edge weights \(w(e)\), for a query \((l,r)\) compute:

[ \text{Answer} = \sum_{l \leq i < j \leq r} d(\text{pos}(i), \text{pos}(j)) ]

where \(d(u,v)\) is the sum of weights on the unique simple path from node \(u\) to node \(v\), and \(\text{pos}(i)\) denotes the unique node with label \(i\).

inputFormat

The first line contains two integers \(n\) and \(m\) - the number of nodes and the number of queries, respectively.

The second line contains \(n\) integers representing the permutation of \(1\) to \(n\); the \(i\)th integer is the label assigned to node \(i\).

The next \(n-1\) lines each contain three integers \(u\), \(v\), and \(w\) indicating that there is an undirected edge between node \(u\) and node \(v\) with weight \(w\).

The following \(m\) lines each contain two integers \(l\) and \(r\), representing a query.

outputFormat

For each query, output a single integer – the sum of distances between all pairs of nodes whose labels lie in the interval \([l, r]\), considering only pairs \((i, j)\) with \(i < j\).

sample

3 2
2 1 3
1 2 1
2 3 2
1 2
1 3

1
6