题意：一棵树，以结点1为根结点悬挂在墙上，每个点有一个权值。选两条边切断，要求：刚好掉下两份结点，且两份不能属于同一子树。求两份结点可能的最大权值和。
tags：裸的树dp。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005; const ll inf= -1e18; int n; ll sz[N], dp[N][2]; //dp[u][0]表示u子树上只取下一份子树的最大值，dp[u][1]表示u子树上必须取下两份子树的和的最大值 vector<int > G[N]; void dfs(int u, int fa) { dp[u][0]=dp[u][1]=inf; for(auto v : G[u]) if(v!=fa) { dfs(v, u); sz[u]+= sz[v]; dp[u][1]=max(dp[u][1], dp[v][1]); //状态转移 if(dp[u][0]!=inf) dp[u][1]=max(dp[u][1], dp[u][0]+dp[v][0]); dp[u][0]=max(dp[u][0], dp[v][0]); } dp[u][0]=max(dp[u][0], sz[u]); } int main() { scanf("%d", &n); rep(i,1,n) scanf("%lld", &sz[i]); int u, v; rep(i,1,n-1) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); if(dp[1][1]==inf) puts("Impossible"); else printf("%lld ", dp[1][1]); return 0; }