(Codeforces) 743D. Chloe and pleasant prizes

http://codeforces.com/problemset/problem/743/D

http://codeforces.com/contest/743/submission/23001469

Tips : DFS !!!

my complexity : O(N lg N)
best : O(N) --- just keep using mx only

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

#define int long long
typedef long long LL;
const LL INF = 1e17 + 7;
const int MAX_N = 2e5 + 6;

struct Node {
    Node *lc,*rc;
    LL val;
    Node() {
        lc=rc=NULL;
        val = -INF;
    }
    void pull() {
        val = max(lc->val,rc->val);
    }
};

vector<int> edg[MAX_N];
LL a[MAX_N];
LL cnt[MAX_N];   //total value XDDD
bool visit[MAX_N];

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) {
        node->val = cnt[L];
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->pull();
    return node;
}

void modify(Node* node, int L,int R,int pos,LL val) {
    if (L==R) {
        node->val = val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos <= mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
    return;
}

LL query(Node* node,int L,int R,int l,int r) {
    if (l>R || L>r) return -INF;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return max(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

struct P {
    int st,ed;
    vector<int> sn;
    int parent;
} p[MAX_N];

void dfs1(int id,int &number,int par) {
    visit[id]=true;
    p[id].parent=par;
    p[id].st=number;
    int hahaha=number;
    cnt[hahaha] = a[id];
    for (auto iter=edg[id].begin();iter!=edg[id].end();iter++) {
        int tmp=*iter;
        if (!visit[tmp]) {
            int hahahaha=number;
            p[id].sn.push_back(tmp);
            number++;
            dfs1(tmp,number,id);
            cnt[hahaha] += cnt[hahahaha+1];
        }
    }
    p[id].ed=number;
}

LL ans;
Node* root;
int n;

void dfs(int id) {
    //cout<<"id = "<<id<<" , st = "<<p[id].st<<endl;
    LL ret=cnt[p[id].st];
    //cout<<"Ret = "<<ret<<endl;
    LL q=max(query(root,1,n,1,p[id].st-1),query(root,1,n,p[id].ed+1,n));
    //cout<<"q = "<<q<<endl;
    if (q==-INF) ;
    else ans = max(ans,ret + q);
    modify(root,1,n,p[id].st,-INF);
    for (auto i=p[id].sn.begin();i!=p[id].sn.end();i++) {
        int tmp=*i;
        dfs(tmp);
    }
    modify(root,1,n,p[id].st,cnt[p[id].st]);
}

main () {
    while (scanf("%I64d",&n) != EOF) {
        root = NULL;
        for (int i=1;n>=i;i++) {
            cnt[i]=0;
            visit[i]=false;
            edg[i].clear();
            p[i].sn.clear();
            scanf("%I64d",&a[i]);
        }
        for (int i=1;n-1>=i;i++) {
            int a,b;
            scanf("%I64d %I64d",&a,&b);
            edg[a].push_back(b);
            edg[b].push_back(a);
        }
        int number=1;
        dfs1(1,number,1);
        //cout<<"innnn\n";
        root = Build(1,n);
        ans = -INF;
        dfs(1);
        if (ans == -INF) puts("Impossible");
        else printf("%I64d\n",ans);
    }
}