QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 512 MB Total points: 100

# 7443. vti

统计

给定一棵包含 $n$ 个结点的树,边的编号从 $1$ 到 $n-1$,第 $i$ 条边有一个权值 $b_i$,树的根节点为 $1$ 号节点;

定义两条边 $x,y$ 构成祖先关系,当且仅当构成边 $x$ 的两个节点中深度最深的一个,是构成边 $y$ 的两个节点中深度最深的一个的祖先。

共 $m$ 次询问,第 $i$ 次询问给出 $t_i$ 个可能相同的点,考虑这些点两两之间简单路径经过的边的并集,问无序地选出两条编号不同的边 $x,y$,使得 $x$ 为 $y$ 祖先,且 $b_x < b_y$ 的方案数。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行,每行两个整数 $a_i,b_i$,表示 $i+1$ 和 $a_i$ 之间有一条边,权值为 $b_i$。

接下来一行一个整数 $m$。

接下来 $m$ 行,每行 $t_i+1$ 个整数,第一个整数为 $t_i$,之后 $t_i$ 个整数表示这次询问的点的集合。

输出格式

对每个询问,输出一行,包含一个整数,表示答案。

样例数据

样例输入

5
1 1
2 2
3 4
1 3
3
1 1
2 1 3
3 3 4 5

样例输出

0
1
3

子任务

Idea:nzhtl1477,Solution:nzhtl1477,Code:ccz181078,Data:nzhtl1477

对于 $100\%$ 的数据,满足 $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$,以上所有数值为整数。