- #include"iostream"
- #include "string.h"
- #include "stack"
- #include "queue"
- #include "string"
- #include "vector"
- #include "set"
- #include "map"
- #include "algorithm"
- #include "stdio.h"
- #include "math.h"
- #definell long long#definebug(x) cout<#definemem(a) memset(a,0,sizeof(a))using namespace std;
- ll ai[200010];
- constll INF=1e18;
- struct Edge{
- int to,next;
- };
- Edge e[400010];
- inthead[200010],tot;
- void add(ll u, ll v){
- e[tot].to=v;
- e[tot].next=head[u];
- head[u]=tot++;
- }
- ll sum[200010];
- void dfs(ll u, ll fa){
- sum[u]=ai[u];
- for(ll i=head[u]; i!=-1; i=e[i].next){
- ll v=e[i].to;
- if(fa==v)continue;
- dfs(v,u);
- sum[u]+=sum[v];
- }
- }
- ll dp[200010][5];
- void dpans(ll u, ll fa){
- //ll ma=-INF;
- for(ll i=head[u]; i!=-1; i=e[i].next){
- ll v=e[i].to;
- if(v==fa)continue;
- dpans(v,u);
- dp[u][2]=max(dp[u][2],dp[v][2]);
- if(dp[u][1]!=-INF)
- dp[u][2]=max(dp[u][2],dp[v][1]+dp[u][1]);
- dp[u][1]=max(dp[u][1],dp[v][1]);
- }
- dp[u][1]=max(dp[u][1],sum[u]);
- }
- int main(){
- int n,a,b;
- scanf("%d",&n);
- memset(head,-1,sizeof(head));
- mem(ai),mem(e),mem(sum);
- for(ll i=1; i<=n; ++i){
- scanf("%lld",&ai[i]);
- dp[i][1]=-INF;
- dp[i][2]=-INF;
- }
- for(ll i=1; ii){
- scanf("%d%d",&a,&b);
- add(a,b);
- add(b,a);
- }
- dfs(1,1);
- dpans(1,1);//for(int i=1; i<=n; i++) cout<<endl<<dp[i][2]<<" "; cout<<endl;
- if(dp[1][2]==-INF) {cout<<"Impossible"<return 0;}
- printf("%lld\n",dp[1][2]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2026233.html