https://ac.nowcoder.com/acm/contest/97017/G
第一次dp1，考虑状态为：$dp[i] = 以i为根的子树，能获得的最大点权和$。
易知所有小于0的dp1状态不需要考虑。
状态转移为：
1.如果不删去点i，$$dp[i] = a[i] +\sum_{v\in uson} dp[v]*(dp[v]>0) $$
2.如果删去点i，因为存在父节点，所以只能保留一条连向父节点的边，即只能是子树dp1的最大值。$$dp[i] = max\{dp[v]*(dp[v]>0)\}v\in uson$$

这个dp没有考虑i子树以外的元素，所以不是最终的答案。
考虑最终的答案，如果以i为根考虑（包含了所有节点），答案除了dp1[i]，还可以是其中两个子树的dp1的和。因此第二步运行换根dp。
需要一个up[i]，表示i节点子树以外的树，的最大点权和。
up的维护方式：
1.如果保留父节点：$$up[i] = a[fa] - dp1[i]+up[fa]+\sum_{v\in fa’son} dp1[v]$$
2.如果不保留父节点：$$up[i] = max(dp1[v],up[fa])，dp1[v]是fa所有子节点dp1值中，除了dp1[i]的最大的dp1$$

以i为根的子树，最大点权和为:
1.如果保留i点:
$dp2[i] = a[i] + \sum_{v\in uson} dp1[v]+up[i]$
2.如果不保留i点，则是所有子树$dp1$值，和$up[i]$的前二大值之和。
3.最终答案为所有dp2中的max。

具体实现：
1.使用multiset的话就不用维护mx1，mx2了，太麻烦。
2.up的状态转移，发现都是用的父节点的值，因此应该在父节点的dfs中更新子节点的up值。
3.注意multiset里的元素个数。为了防止multiset空，以及元素个数不好计算。所有小于0的dp值当做0插入。

#include<bits/stdc++.h>
#define endl '\n'


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define MULTI_TEST
//dp1是以i为根的子树，能构成的最大点权和
//up是i点往上，能构成的最大点权和。
vector<ll> dp1,dp2;
vector<vector<int>> g;
vector<ll> up;
vector<ll> a;
int n;

void solve(){
    cin>>n;
    g = vector<vector<int>>(n+1);
    up = a = dp1 = dp2 = vector<ll>(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto dfs1=[&](auto &&dfs1,int u,int fa)->void{
        ll sum = 0;
        ll mx = 0;
        for(auto v:g[u]){
            if(v==fa) continue;
            dfs1(dfs1,v,u);
            sum += max(0ll,dp1[v]);
            mx = max(mx,dp1[v]);
        }
        dp1[u] = max(sum+a[u],mx);
    };
    dfs1(dfs1,1,-1);
    ll ans = -1e18;
    auto dfs2=[&](auto &dfs2,int u,int fa)->void{
        std::multiset<ll, std::greater<>> ms;
        ll sum = max(0ll,up[u]) + a[u];
        if(up[u]>=0) ms.insert(up[u]); //=0 也插入，因为插入后没影响。但是如果都小于0的话还能防止错误。
        for(auto v:g[u]){
            if(v==fa) continue;
            sum +=max( 0ll,dp1[v]);
            ms.insert(max(0ll,dp1[v]));
             //小于0就当成0都插入，这样后面就不用特判
        }
        ll del = 0;
        if(ms.size()>1){
            del = *ms.begin() + *next(ms.begin());
        }else del = *ms.begin();
        dp2[u] = max(sum,del);
        for(auto v:g[u]){
            if(v==fa) continue;
            ms.erase(max(0ll,dp1[v]));
            up[v] = max(sum-max(0ll,dp1[v]),*ms.begin());
            dfs2(dfs2,v,u);
            ms.insert(max(0ll,dp1[v]));
        }
    };
    dfs2(dfs2,1,-1);
    for(int i=1;i<=n;i++) ans=max(ans,dp2[i]);
    cout<<ans<<endl;
}

int main(){     
    ifstream test_file("in.txt");
    if (test_file) {
        freopen("in.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}