J-Re:从零开始的近世代数复习（hard）_河南萌新联赛2025第（五）场：信息工程大学”

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

期末考还有最后一门考试--近世代数，但是小明还在进行出题，他必须从零开始复习近世代数。近世代数是一门非常复杂的课，挂科率很高，小明决定找到最优的复习策略。

假设近世代数中有n个不同的定理1到n，每个定理有不同的难度，导致每个定理复习需要时间不同，其中第i个定理需要的复习时间是 $a_i$ ，且复习一个定理需要先知道它的前置定理，所有定理可以连接成一颗有根树，定理1为根节点，一个除根以外的定理x可以被复习当且仅当它的父节点已经被复习过了，根节点可以直接进行复习

现在小明一个定理都还没有复习，但他有q种复习策略，每种策略有k个定理是重要考点，他希望能够复习到这k个定理，不过时间不够了，他希望花费最少的时间去复习到这k个定理，请你对每种策略求出复习到该策略中的k个定理所需要的最短时间是多少。

本题与easy版本的唯一区别在于本题的k范围是1<=k<=10^5

输入描述:

输入描述

第一行输入定理个数n

第2行输入n个数，第i个数代表定理i的复习时间 $a_i$

接下来n-1行每行输入两个数u v，代表u是v的父节点

下一行输入一个数q代表复习策略数

对每种策略，先输入一个数k代表该策略重要定理数

再在下一行输入k个数代表需要复习的重要定理

输出描述:

对每种策略输出一行一个整数代表最短复习时间

示例1

输入

复制

输出

复制

6
15

备注:

数据范围：

$1\le n,q \le 10^5$
$1\le a_i\le10^9$
$1\le k\le n$

保证单个测试文件 $\sum k \le 2 \times 10^5$