E-树的直径_牛客练习赛54

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

题目描述

小a觉得求一棵树的直径太naive了，于是在树上划掉了几条边，想求所有连通块的直径。
给定一棵n个点的树，每个点有权值f[i]。
q次询问，每次询问给定k条边，求删除这k条边之后，剩下k+1个连通块的直径。你只需要输出这k+1个连通块直径的异或和即可。
记dis(u,v)为 $u\to v$ 的简单路径上，所有边的边权和。(u,v)间距离DIS(u,v)的定义为： $DIS(u,v)=\begin{cases}0,&u=v\\f[u]+f[v]+dis(u,v),&u\neq v\end{cases}$
某个连通块S的直径定义为： $\max_{u\in S,v\in S}\{DIS(u,v)\}$ 。
询问间互不影响，即当前删除某些边对下一次询问没有影响。

输入描述:

第一行两个整数n,q，表示树的点数及询问次数。
接下来一行有n个整数，表示每个点的点权f[i]。
接下来n-1行，每行三个整数u,v,w，表示u,v间有一条权值为w的无向边。
接下来2q行，每两行格式如：第一行一个整数，表示要删掉的边的数量；第二行2k个整数，表示要删掉的第i条边是之间的边。保证每对二元组互不相同。

输出描述:

输出q行。对于每次询问，输出一个整数表示k+1个连通块的直径的异或和。

示例1

输入

复制

7 2
1 2 3 1 2 3 4
1 2 2
2 3 1
2 4 3
2 5 2
1 6 2
1 7 2
1
1 2
2
2 4 1 7

输出

复制

3
11

备注:

。
输入数据量可能较大，建议使用较快的读入方式。