- #include
- using namespace std;
- #pragmacomment(linker, "/STACK:102400000,102400000")#definerep(i,a,b) for (int i=a;i<=b;i++)#defineper(i,b,a) for (int i=b;i>=a;i--)#definemes(a,b) memset(a,b,sizeof(a))#defineINF 0x3f3f3f3f
- typedef long long ll;
- const intN =200005;
- constll inf= -1e18;
- int n;
- ll sz[N], dp[N][2];//dp[u][0]表示u子树上只取下一份子树的最大值,dp[u][1]表示u子树上必须取下两份子树的和的最大值vector<int> G[N];
- voiddfs(intu,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");
- elseprintf("%lld\n", dp[1][1]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2023899.html