mhy住在一棵有n个点的树的1号结点上，每个结点上都有一个妹子i。

mhy从自己家出发，去给每一个妹子都送一台电脑，每个妹子拿到电脑后就会开始安装zhx牌杀毒软件，第i个妹子安装时间为Ci。

树上的每条边mhy能且仅能走两次，每次耗费1单位时间。mhy送完所有电脑后会回自己家里然后开始装zhx牌杀毒软件。

卸货和装电脑是不需要时间的。

求所有妹子和mhy都装好zhx牌杀毒软件的最短时间。

6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6

11

设f[x]为x的子树中全部安完软件的时间，

设他们的子树大小为size[a],size[b]，分为两种情况：

先走a，后走b，f[x]=max(f[a]+1,f[b]+2*size[a]+1)
先走b，后走a，f[x]=max(f[a]+2*size[b]+1,f[b]+1)

(记得+1)

f[a]+1和f[b]+1不用考虑，那么如果先走a更优：

f[b]+2*siz[a]+1<f[a]+2*siz[b]+1

化简得到

f[a]-2*siz[a]>f[b]-2*siz[b]

排序f[i]-2*siz[i]即可。

根节点的软件是最后安装的，所以要最后特判一下。

#include
#include
#include
#include
using namespace std;
const int maxn=500010;
int n,cnt;
int to[maxn<<1],nxt[maxn<<1],head[maxn],v[maxn],p[maxn],f[maxn],siz[maxn];

void add(int a,int b){
to[cnt]=b;
nxt[cnt]=head[a];
head[a]=cnt++;

}

bool cmp(int a,int b){
return f[a]-2*siz[a]>f[b]-2*siz[b];
}

void dfs(int x,int fa){
int i,sum=0;
siz[x]=1;
for(i=head[x];i!=-1;i=nxt[i])
if(to[i]!=fa)
dfs(to[i],x),siz[x]+=siz[to[i]];

p\[0\]=0;

for(i=head\[x\];i!=-1;i=nxt\[i\])  
    if(to\[i\]!=fa)  
        p\[++p\[0\]\]=to\[i\];

sort(p+1,p+p\[0\]+1,cmp);

if(x!=1)f\[x\]=v\[x\];

for(i=1;i<=p\[0\];i++)  
    f\[x\]=max(f\[x\],f\[p\[i\]\]+sum+1),sum+=2\*siz\[p\[i\]\];

}

int main(){
scanf("%d",&n);
int i,a,b;
memset(head,-1,sizeof(head));
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
for(i=1;i<n;i++)
scanf("%d%d",&a,&b),add(a,b),add(b,a);

dfs(1,0);  
printf("%d",max(f\[1\],2\*(siz\[1\]-1)+v\[1\]));  
return 0;  

}

Farmcraft