原题链接：CF1901E，树形 dp + 神奇分类讨论。
很容易想到树形 dp。难点在于如何转移以及统计答案，需要大量分讨。
-
父亲（及其以上）和自己组成连通块，不缩。(只保留自己并且往上传递)
-
连通块中只有自己一个（记录答案）
-
一个儿子和自己组成连通块，且自己作为根节点，不和父亲收缩（记录答案）
-
一个儿子和自己组成连通块，且自己要和父亲收缩（往上转移）
-
两个儿子和自己组成连通块，且和自己的两个儿子收缩，不和父亲收缩（记录答案）
-
两个及以上儿子和自己组成连通块，不缩，可能还会加上父亲（往上转移）
-
三个及以上儿子和自己，不缩，不加父亲（直接记录答案）
需要慢慢理解，具体详见代码。
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return '\n';
}
return *S++;
}
}
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~ NTR() { flush(); }
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar();
while (c == ' ' || c == '\n') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == ' ' || c == '\n') c = getchar();
while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader(){}
} cin;
const char endl = '\n';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45];
int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
} cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
const int MAXN = 5e5 + 10;
int n,a[MAXN],head[MAXN],cnt,x,y,T,dp[MAXN],ans;
struct Node{int u,v,nxt;}e[MAXN << 1];
inline void Add(int u,int v){e[++cnt] = {u,v,head[u]};head[u] = cnt;}
inline void init()
{
for(int i = 1;i <= n;i++) head[i] = -1,a[i] = dp[i] = 0;
cnt = 0,ans = 0;
}
inline void dfs(int u,int father,int root)
{
dp[u] = a[u];//父亲（及其以上）和自己组成连通块，不缩。(只保留自己并且往上传递)
ans = max(ans,dp[u]);//连通块中只有自己一个（记录答案）
vector <int> f;
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(now == father) continue;
dfs(now,u,root),f.emplace_back(dp[now]);
ans = max(ans,dp[now] + a[u]);// 一个儿子和自己组成连通块，且自己作为根节点，不和父亲收缩（记录答案）
dp[u] = max(dp[u],dp[now]);//一个儿子和自己组成连通块，且自己要和父亲收缩（往上转移）
}
sort(f.begin(),f.end(),greater<int>());
if(f.size() >= 2)
{
int tmp = f[0] + f[1];
ans = max(ans,tmp);//两个儿子和自己组成连通块，且和自己的两个儿子收缩，不和父亲收缩（记录答案）
for(int j = 2;j < f.size() && f[j] > 0;j++) tmp += f[j];
dp[u] = max(a[u] + tmp,dp[u]);//两个及以上儿子和自己组成连通块，不缩，可能还会加上父亲（往上转移）
}
if(f.size() >= 3)
{
int tmp = f[0] + f[1] + f[2];
for(int j = 3;j < f.size() && f[j] > 0;j++) tmp += f[j];
ans = max(ans,a[u] + tmp);//三个及以上儿子和自己组成连通块，不缩，不加父亲（直接记录答案）
}
}
signed main()
{
cin >> T;
while(T--)
{
cin >> n;init();
for(int i = 1;i <= n;i++) cin >> a[i];
for(int i = 1;i < n;i++) cin >> x >> y,Add(x,y),Add(y,x);
dfs(1,0,1);
cout << ans << endl;
}
return 0;
}