C · Cut Tree：中文题面

时限 10 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

给定一棵 $n$ 个顶点的树，顶点 $i$ 的权值为 $z_i$ 。边按输入次序编号为 $1,\ldots,n-1$ 。

每个询问给出 $l,r,f$ ，满足 $1\le l\le f\le r\le n-1$ 。保留编号在 $[l,r]$ 内的边，但删除编号为 $f$ 的边；区间外的边也不保留。所有 $n$ 个顶点仍然存在，得到一个森林。连通块权值为块内所有顶点权值之和，孤立顶点单独构成一个块。输出最大连通块权值。

各询问相互独立，不会累积删边。

输入、输出与约束 #

$1\le T\le10^5$ 。每组先输入 $2\le n\le2\times10^5$ ，随后 $n-1$ 行输入边端点 $u_i,v_i$ ，编号均在 $[1,n]$ 内且不同，保证成树。再输入 $n$ 个点权 $1\le z_i\le100$ 。接着输入 $1\le q\le2\times10^5$ 及 $q$ 行询问 $l,r,f$ 。

单个测试文件中 $\sum n\le2\times10^5$ 、 $\sum q\le2\times10^5$ 。每个询问输出一行整数。

样例 #

输入 1 #

2
5
1 2
2 3
3 4
4 5
10 20 30 40 50
3
1 4 2
2 4 4
1 1 1
2
1 2
7 5
1
1 1 1

输出 1 #

样例说明 #

第一组是点权 $10,20,30,40,50$ 的五点链。询问 $(1,4,2)$ 保留边 $1,3,4$ ，两块权值为 $30,120$ ，答案 $120$ ； $(2,4,4)$ 保留边 $2,3$ ，最大块为顶点 $2,3,4$ ，权值 $90$ ； $(1,1,1)$ 不留任何边，答案为最大点权 $50$ 。第二组也删除唯一一条边，答案为 $\max(7,5)=7$ 。

整理进度 #

本批材料没有这道题的个人 C++ 文件，因此这里先保留中文题面与样例解释；不把题面整理记作已补题。赛时提交过程与赛后补题记录待补。