P8205 [Ynoi2005] vti

Given a tree with $n$ nodes, the edges are numbered from $1$ to $n-1$. The $i$-th edge has a weight $b_i$. The root of the tree is node $1$. Define that two edges $x, y$ have an ancestor relationship if and only if, among the two endpoints of edge $x$, the deeper node is an ancestor of the deeper node among the two endpoints of edge $y$. There are $m$ queries. In the $i$-th query, $t_i$ (possibly repeated) nodes are given. Consider the union of edges on the simple paths between every pair of these nodes. Among these edges, count the number of ways to choose two unordered edges $x, y$ with different indices such that $x$ is an ancestor of $y$, and $b_x < b_y$.

The first line contains an integer $n$. The next $n-1$ lines each contain two integers $a_i, b_i$, meaning that there is an edge between $i+1$ and $a_i$, with weight $b_i$. The next line contains an integer $m$. The next $m$ lines each contain $t_i+1$ integers. The first integer is $t_i$, followed by $t_i$ integers representing the set of nodes in this query.

For each query, output one line containing one integer, the answer.

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: nzhtl1477. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le a_i \le i-1$, $1 \le b_i \le n$, $1 \le t_i$, $t_1 + \dots + t_m \le 10^6$. All values above are integers. Translated by ChatGPT 5