[Poi2014]FarmCraft

首先，每条边只能被走两次，就是一遍dfs，

求f[x],f[x]代表以x为节点的子树遍历完需要的步数

显然，对于叶子节点，f[x]=0;

我们维护一个rest[x],代表假设x为根节点，遍历完子树后，还需要多长时间完成所有安装

显然ans=max(rest[1],c[1]);每个节点的rest由子节点更新

对于节点x，把它子节点的rest排序，先走大的肯定是最优的，rest[x]=max{max{rest[son[x]]-ti}，c[x]-f[x]}

ti代表遍历完这个子节点后走其他子节点还需要走的步数,对于叶节点，rest[x]=c[x];

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N  500005
using namespace std;
int n,m;
int c[N],f[N],fa[N];
bool vis[N];
struct edge
{ 
    int to,ne;  
}b[N*2];
struct node
{
    int f,rest;  
};
int k=0,head[N];
void add(int x,int y)
{
     b[k].to=y;b[k].ne=head[x];head[x]=k++;
}
void dfs(int now,int father)
{
     fa[now]=father;
     f[now]=0;
     for(int i=head[now];i!=-1;i=b[i].ne)
     if(b[i].to!=father){
        dfs(b[i].to,now);
        f[now]+=f[b[i].to]+2;
     }
}
int comp_(const node &w,const node &e)
{
     return w.rest>e.rest;
}
int dp(int x)
{
    if(f[x]==0) return c[x];
    vector<node> g;
    node tmp;
    int js=0,sum=f[x];
    for(int i=head[x];i!=-1;i=b[i].ne)
    if(b[i].to!=fa[x]){
       tmp.rest=dp(b[i].to);
       tmp.f=f[b[i].to];
       g.push_back(tmp);
    }
    int ans=0,ti=0;
    sort(g.begin(),g.end(),comp_);
    for(int i=0;i<g.size();i++)
    {
      int t=sum-ti-g[i].f-1;
      ans=max(max(0,g[i].rest-t),ans);
      ti+=(g[i].f+2);
    }
    if(x==1) ans=max(ans,c[1]);
    else  ans=max(ans,max(c[x]-f[x],0));
    return ans;
}
int main()
{
    int x,y;
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
       scanf("%d",&c[i]);
    }
    for(int i=1;i<n;i++){
       scanf("%d%d",&x,&y);
       add(x,y); add(y,x);
    }
    dfs(1,0);
    int ans=dp(1)+2*(n-1);
    printf("%d\n",ans);
    while(1);
    return 0;
}