题目背景

题目描述

给定一棵树，点有整数点权。现在可以修改其中一个点的权值为任意整数，请找到一种修改方案，使得修改前的任意一个最大权独立集与修改后的任意一个最大权独立集间相差的点数的最少可能值尽可能大。你只需要求出这个最大可能值。

形式化题意

记树为 $T(V,E)$，其中 $V=\{1,2,\dots,n\}$ 为树的点集，$E\subset V\times V$ 为树的边集。定义点权为一个函数 $v:V\to\Z$，表示点 $i$ 的权值为 $v(i)$。修改后的权值应为一个函数 $v':V\to\Z$，满足 $\exists u\in V,\forall i\in V-\{u\},v'(i)=v(i)$，即除了某个 $u$ 以外其他点的权值均不变。

定义一个独立集 $S\subset V$ 为点集的一个子集，满足 $\forall i,j\in S,(i,j)\notin E$。定义独立集 $S$ 的权值 $\mathfrak{v}_ v(S):=\sum_{i\in S}v(i)$。权值函数 $v$ 对应的最大权独立集为使得 $\mathfrak{v}_ v(S)$ 最大的独立集，即其权值为 $\mathfrak{V}_ v(T):=\max_{S\subset V, S 为独立集}\{\mathfrak{v}_ v(S)\}$，有可能有多个。所有最大权独立集构成的集合族为 $\mathfrak{S}_ v(T)=\left\{S\subset V:\mathfrak{v}_ v(S)=\mathfrak{V}_ v(T)\right\}$。

定义 $f_T(v,v')=\min_{S\in\mathfrak{S}_ v(T),S'\in\mathfrak{S}_ {v'}(T)}\left\lvert S\Delta S'\right\rvert$，其中 $|S|$ 表示集合 $S$ 的大小，$\Delta$ 表示对称差运算。请求出 $\max_{v'}f_T(v,v')$ 的值。

输入格式

第一行输入一个正整数 $t$ 表示数据组数。

每组数据第一行输入一个正整数 $n$ 表示树的结点数。

第二行输入 $n$ 个整数 $v(1).\dots,v(n)$，表示点的权值。

接下来 $n-1$ 行，每行输入两个整数 $x,y$ 表示 $x,y$ 之间有一条树的边。

输出格式

对于每组数据，输出一行，一个整数表示答案。

2
4
1 2 3 4
1 4
2 4
3 4
10
3 2 7 -2 4 -1 10 0 5 1
1 7
2 3
3 7
3 4
5 6
5 7
7 9
8 10
9 10

4
7

提示

样例解释

对于第一组数据，修改前的最大权独立集只能为 $\{1,2,3\}$。若只修改点 $1$ 的权值，则修改后仍存在一个最大权独立集包含 $2,3$ 且不包含 $4$；若只修改点 $2$ 的权值，则修改后仍存在一个最大权独立集包含 $1,3$ 但不包含 $4$。故相差点数的最少可能值不超过 $1$。

若将点 $3$ 的权值修改为 $0$，则修改后的最大权独立集只有 $\{4\}$；若将点 $4$ 的权值修改为 $7$，则修改后的最大权独立集同样只有 $\{4\}$。此时相差点数必定为 $4$，即为所求的最大可能值。

对于第二组数据，将结点 $7$ 的权值修改为 $17$，则修改前的最大权独立集可能为 $\{1,3,5,9\}$ 或 $\{1,3,5,8,9\}$，修改后的最大权独立集只有 $\{2,7,10\}$，最少相差点数为 $7$。可以证明这是最大可能值。

数据范围与限制

本题采用捆绑测试，各 Subtask 的限制与分值如下。

特殊性质 A：存在一个 $1$ 到 $n$ 的排列 $p$，对于 $1\le i<n$，结点 $p_i$ 与 $p_{i+1}$ 间有一条边；

特殊性质 B：存在一个结点与所有其他结点间均有边。

对于所有数据，满足 $1\le t\le10$，$1\le n\le10^6$，$-10^9\le v(i)\le10^9$，$\sum n\le10^6$。