P7880 [Ynoi2006] rldcot

Given a tree with $n$ nodes, the root is $1$. Each node has an index, and each edge has a weight. Define $dep(x)$ as the sum of edge weights on the simple path from node $x$ to the root, and $lca(x,y)$ as the lowest common ancestor of nodes $x$ and $y$ in the tree. There are $m$ queries. In each query, $l,r$ are given. For all ordered pairs of node indices $(i,j)$ satisfying $l \le i,j \le r$, ask how many distinct values of $dep(lca(i,j))$ there are.

The first line contains two integers $n,m$ separated by spaces. The next $n-1$ lines each contain three integers $u,v,d$ separated by spaces, meaning there is an edge from $u$ to $v$ with weight $d$. The next $m$ lines each contain two integers $l,r$ separated by spaces, representing one query.

Output $m$ lines. Each line contains one integer, the answer to the corresponding query.

Idea: nzhtl1477, Solution: nzhtl1477, Code: lk, Data: nzhtl1477. Constraints: For $10\%$ of the testdata, $1 \le n,m \le 100$. For another $20\%$ of the testdata, $1 \le n,m \le 5000$. For another $20\%$ of the testdata, $1 \le n,m \le 50000$. For another $20\%$ of the testdata, $d=1$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$, all values are integers, and $-10^9 \le d \le 10^9$. Translated by ChatGPT 5