（感觉洛谷上题面那一小段中文根本看不懂啊，好多条件都没讲，直接就是安装也要一个时间啊，，，明明不止啊！还好有百度翻译。。。。。。）
题意：一棵树，一开始在1号节点（root），边权都为1，每个点有点权，要最小化max(点权+到达时间） <---所有点的
首先这看起来就是一道DP题，但是根据直觉，，，应该跟贪心挂钩，因为感觉耗时久的要先去是吧
但是我们发现并不能这么弄，因为去一棵子树就要走完它，这个时候再去别的树的时候可能已经很晚了，所以就不一定优了
不过我们可以发现，从一个点出发，去节点的顺序就决定了答案
于是我们考虑排序
但是节点太多比较难以分析，因此我们先以两个儿子为例分析。
f[i]代表以i为根的最大时长，
于是目的就是最小化f[1],size[i]代表遍历这个点要多久，
因为要遍历完这个子树才可以去另一棵，于是就有转移方程：
f[i]=max(f[a],f[b] + size[a] + 2),其中a，b为两棵子树，+2是去a的那条边来回的时间，这个是先去a的，
f[i]=max(f[b],f[a] + size[b] + 2),然后就是最小化这4个式子中的最大值，
PS:等等，，，貌似是f[a]+1????，懒得改了，，，大家自行脑补成f[a]+1吧，不影响结果
于是先按照国王游戏里面的方法来推导一下:
首先设先去a比较优，
那么有max(f[a],f[b] + size[a] + 2) < max(f[b],f[a] + size[b] + 2)
因为f[a] + size[b] + 2 > f[a],f[b] + size[a] + 2 > f[b],
所以这4个式子的最大值不可能会是f[a] or f[b],
所以要使得等式成立就只能寄希望于
f[b] + size[a] + 2 < f[a] + size[b] + 2
所以以这个为条件排序即可
各种细节QAQ调了好久
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 501000 5 #define getchar() *o++ 6 #define LL long long 7 char READ[40001000],*o=READ; 8 int n,ans; 9 int cost[AC],size[AC]; 10 int date[AC * 2],Next[AC * 2],Head[AC],tot; 11 struct point{ 12 int size; 13 LL f; 14 }p[AC]; 15 LL f[AC]; 16 inline int read() 17 { 18 int x=0;char c=getchar(); 19 while(c > '9' || c < '0') c=getchar(); 20 while(c >= '0' && c <= '9') x=x*10+c-'0',c=getchar(); 21 return x; 22 } 23 24 inline void add(int f,int w) 25 { 26 date[++tot]=w,Next[tot]=Head[f],Head[f]=tot; 27 date[++tot]=f,Next[tot]=Head[w],Head[w]=tot; 28 } 29 30 inline bool cmp(point a,point b) 31 { 32 return b.f + a.size < a.f + b.size; 33 } 34 35 void pre() 36 { 37 R a,b; 38 n=read(); 39 for(R i=1;i<=n;i++) cost[i]=read(); 40 for(R i=1;i<n;i++) 41 { 42 a=read(),b=read(); 43 add(a,b); 44 } 45 } 46 47 void DFS(int x,int fa)//还是要传father，不然的话下面加入队列的部分就判断不了了，因为这时下面都已经访问过了 48 { 49 int now,tot=0; 50 if(x != 1) f[x] = cost[x];//至少自己要装啊,但是注意第一个是最后装的 51 for(R i=Head[x]; i ;i=Next[i]) 52 { 53 now=date[i]; 54 if(now == fa) continue; 55 DFS(now,x); 56 } 57 for(R i=Head[x]; i ;i=Next[i]) 58 { 59 now=date[i]; 60 if(now != fa) 61 p[++tot]=(point) {size[now],f[now]};//不能在上面加，因为一旦下一次调用了DFS，队列里就乱了 62 } 63 sort(p+1,p+tot+1,cmp); 64 for(R i=1;i<=tot;i++) 65 { 66 f[x]=max(f[x],p[i].f + size[x] + 1); 67 size[x] += p[i].size + 2;//反正这样也是统计了一样的东西 68 } 69 } 70 71 int main() 72 { 73 freopen("in.in","r",stdin); 74 fread(READ,1,40000000,stdin); 75 pre(); 76 DFS(1,0); 77 printf("%lld ",max(f[1],(LL)(n * 2 - 2 + cost[1]))); 78 fclose(stdin); 79 return 0; 80 }