[Poi2014]FarmCraft 树状dp

对于每个点，处理出走完其子树所需要的时间和其子树完全下载完软件的时间

易证，对于每个点的所有子节点，一定优先选择差值大的来给后面的时间

树规+贪心。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<queue>

#define N 500005

using namespace std;

int e=1,head[N],fa[N],n;

int a[N];

struct edge{

    int u,v,next;

}ed[2*N];

void add(int u,int v){

    ed[e].u=u; ed[e].v=v;

    ed[e].next=head[u];

    head[u]=e++;

}

struct data{

    int f,g,del;//f为出该子树用的时间，g为该子树装完软件的时间，del为差值；

    bool operator < (const data &a) const{

        return a.del>del;

    }

}da[N];

int q[N],top=0;

bool cmp(int x,int y)

{return da[x].del<da[y].del;}

void dfs(int x){

    int bottom=top;

    for(int i=head[x];i;i=ed[i].next){

        int v=ed[i].v;

        if(v==fa[x]) continue;

        fa[v]=x;

        dfs(v);

        q[++top]=v;

    }

    if(x!=1){

        da[x].g=1+a[x];

        da[x].f++;

    }

    sort(q+bottom+1,q+top+1,cmp);

    while(top>bottom){

        da[x].g=max(da[x].g,da[x].f+da[q[top]].g);

        da[x].f+=da[q[top]].f;

        top--;

    }

    if(x==1){da[x].g=max(da[x].g,da[x].f+a[x]);}

    if(x!=1) da[x].f++;

    da[x].del=da[x].g-da[x].f;

}

int main()

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d",&a[i]);

    int u,v;

    for(int i=1;i<n;i++){

        scanf("%d%d",&u,&v);

        add(u,v); add(v,u);

    }

    dfs(1);

    printf("%d\n",da[1].g);

    return 0;

}