Explanation: Byteasar should deliver the computers to the houses in the following order: 3, 2, 4, 5, 6, and 1. The game will be installed after 11, 10, 10, 10, 8, and 9 minutes respectively, in the house number order. Thus everyone can play after 11 minutes.
If Byteasar delivered the game in the following order: 3, 4, 5, 6, 2, and 1, then the game would be installed after: 11, 16, 10, 8, 6, and 7 minutes respectively. Hence, everyone could play only after 16 minutes,
题解：设f[x]为x的子树中全部安完软件的时间，对于x节点的a,b儿子，设他们的子树大小为siz[a],siz[b]，显然遍历一遍子树a的时间就是2*siz[a]，然后分类讨论
若先走a，后走b，那么f[x]=max(f[a]+1,f[b]+2*siz[a]+1)
若先走b，后走a，那么f[x]=max(f[a]+2*siz[b]+1,f[b]+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]
那么直接将x的儿子按照f[i]-2*siz[i]排序，先走f[i]-2*siz[i]的就好了
注意根节点要特判，ans=max(2*(n-1)+1+time[1]，f[1])
代码：
1 #include <cstdio>
2 #include <iostream>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 const int maxn=500000+3;
7 int n,cnt;
8 int to[maxn*2],next[maxn*1],head[maxn],v[maxn],p[maxn],f[maxn],siz[maxn];
9 void add(int a,int b){//前向星存储
10 to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
11 }
12 bool cmp(int a,int b){
13 return f[a]-2*siz[a]>f[b]-2*siz[b];
14 }
15 void dfs(int x,int fa){
16 int i,sum=0;
17 siz[x]=1;
18 for(i=head[x];i!=-1;i=next[i])
19 if(to[i]!=fa){
20 dfs(to[i],x);
21 siz[x]+=siz[to[i]];
22 }
23 p[0]=0;
24 for(i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) p[++p[0]]=to[i];
25 sort(p+1,p+p[0]+1,cmp);// 给子树排序，确定先走哪一条路
26 if(x!=1) f[x]=v[x];
27 for(i=1;i<=p[0];i++) {
28 f[x]=max(f[x],f[p[i]]+sum+1);
29 sum+=2*siz[p[i]];
30 }
31 }
32 int main(){
33 // freopen("1.in","r",stdin);
34 scanf("%d",&n);
35 int i,a,b;
36 memset(head,-1,sizeof(head));
37 for(i=1;i<=n;i++) scanf("%d",&v[i]);
38 for(i=1;i<n;i++) scanf("%d%d",&a,&b),add(a,b),add(b,a);
39 dfs(1,0);
40 printf("%d",max(f[1],2*(siz[1]-1)+v[1]));
41 return 0;
42 }
View Code
