题目链接
大概题意：
给你一棵树，求两颗不相交的子树使它们的点权总和最大，输出最大的点权和。点权可能为负。
输入：输入N，N表示树节点的位置，接下来一个输入N个数分别表示节点的权值，接下来N-1行输入两个数表示这两个点存在一条无向边。
输出：输出两颗不相交的子树使它们的点权总和最大。

思路：
总体思路用树状数组。第一遍dfs求出以每个节点为根节点的树的点权和，用f数组存下来。第二遍dfs用DP数组存下以各个节点为根节点的树的所有子树的点权和的最大值。

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const ll minx=-1e18;
//const ll maxx=1e18;
int n;
int a[200005];
vector<int  > g[200005];
ll f[200005];//f数组记录着以x为根节点的树上各点的点权和 
ll dp[200005];//dp数组表示以x为根节点的树中，所有子树存在的最大的点权和
ll ans=minx;
ll max(ll a,ll b){
    if(a>=b) return a;
    return b;
} 
ll dfs1(int fa,int x){//求以各个节点的根的树的点权和
    int len=g[x].size();
    if(len==1&&x!=1){
        f[x]=a[x];
        return f[x];
    }
    ll sum=a[x];
    for(int i=0;i<len;i++){
        if(g[x][i]==fa) continue;
        ll temp=dfs1(x,g[x][i]);
        sum+=temp;
    }
    f[x]=sum;
    return f[x];
}
ll dfs2(int fa,int x){
    int len=g[x].size();
    if(len==1&&x!=1){
        dp[x]=f[x];
        return dp[x];
    }
    dp[x]=f[x];//这步很重要
    ll max1=minx,max2=minx,temp;//max1表示最大值，max2表示次大值
    for(int i=0;i<len;i++){
        if(g[x][i]==fa) continue;
        temp=dfs2(x,g[x][i]);
        if(temp>max1){//如果子树的最大点权和比最大值大，更新最大值
            max2=max1;//**同时更新最小值**
            max1=temp;
        }
        else{//如果比最大值小，那么就与次小值比较，更新次小值
            max2=max(max2,temp);
        }
//dp[x]取以x为根节点的树中，所有子树存在的最大的点权和
        dp[x]=max(dp[x],temp);
    }
//如果max1和max2都被更新了，那么说明以x为根节点会存在两个不相连的子树，那么更新ans值
    if(max1!=minx&&max2!=minx){
        ans=max(ans,max1+max2);
    }
    return dp[x];
} 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(0,1);
    dfs2(0,1);
    if(ans==minx) cout<<"Impossible"<<endl;
    else cout<<ans<<endl;
    return 0;
}