[POI2014]FAR-FarmCraft

mhy住在一棵有 n$n$ 个点的树的 1$1$ 号结点上，每个结点上都有一个妹子。
mhy从自己家出发，去给每一个妹子都送一台电脑，每个妹子拿到电脑后就会开始安装zhx牌杀毒软件，第i个妹子安装时间为 Ci$Ci$ 。
树上的每条边 mhy$mhy$ 能且仅能走两次，每次耗费 1$1$ 单位时间。mhy送完所有电脑后会回自己家里然后开始装zhx牌杀毒软件。
卸货和装电脑是不需要时间的。
求所有妹子和 mhy$mhy$ 都装好 zhx$zhx$ 牌杀毒软件的最短时间。

n<=500000$n<=500000$

好久之前大概12月集训的一道题？现在看上去是个套路题啊..
显然 每个点一定且最多经过 2$2$ 次, 一次是进到子树中,另一次是从子树中出来。
f[i]$f[i]$表示从 i$i$ 的子树中走出来到 i$i$ 后还要过多久才会安装完毕。
考虑如何从 f[v]$f[v]$ 转移到 f[u]$f[u]$ ,这里有一个显然的贪心,优先走 f[v]$f[v]$ 大的点,然后模拟走的过程转移显然。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=5e5+5;
typedef pair<int,int>par;
#define mp make_pair

struct edge{
    int to,next,w;
}e[MAXN<<1];

int head[MAXN],val[MAXN],f[MAXN],size[MAXN],n,cnt=0;
inline void add(int u,int v,int w){
    e[++cnt]=(edge){v,head[u],1},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],1},head[v]=cnt;
}

vector<par>vec[MAXN];
bool cmp(par a,par b){
    return a.first>b.first;
}

void dfs(int u,int fa){
    size[u]=1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        size[u]+=size[v];
    }
}

void dfs2(int u,int fa){
    if(u!=1)f[u]=val[u]; 
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        dfs2(v,u);
    }
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(v==fa)continue;
        vec[u].push_back(mp(f[v],v));
    }
    sort(vec[u].begin(),vec[u].end(),cmp);
    for(int i=0;i<vec[u].size();i++){
        int v=vec[u][i].second;
        f[u]=max(max(f[v]-1,0),f[u]-(size[v]<<1));
    }
//  f[u]=max(f[u],val[u]);
//  cout<<f[u]<<" "<<u<<endl;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&val[i]);
    }
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v,1);
    }
    dfs(1,1);
    dfs2(1,1);
    cout<<((n-1)*2)+max(f[1],val[1])<<endl;
    return 0;
}