题目大意：给定一棵树，从1号节点出发对树进行欧拉遍历，每到达一个点这个点就开始装MC，每个点装MC的时间不同，最后回到1号节点装MC，求所有人都能联机的最少时间

令f[x]为对第x个节点进行欧拉遍历的时间，g[x]为对第x个节点进行欧拉遍历并完成所有节点的装机的最小时间

那么在每个节点以什么顺序遍历每棵子树呢？

我们发现装机多出来的时间 即g[x]-f[x]可以用来遍历其它子树 那么显然要从g[x]-f[x]大的子树开始遍历

因此对每个节点的子树按照g[x]-f[x]递减排个序即可

时间复杂度O(nlogn) 怎么这么慢……

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 500500 using namespace std; struct abcd{ int to,next; }table[M<<1]; int head[M],tot; int n; int a[M],f[M],g[M]; //f表示遍历所需时间，g表示遍历并装机完毕所需时间 void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } bool Compare(int x,int y) { return g[x]-f[x] > g[y]-f[y]; } void Tree_DP(int x,int from) { int i; for(i=head[x];i;i=table[i].next) if(table[i].to!=from) Tree_DP(table[i].to,x); static int stack[M];int top=0; for(i=head[x];i;i=table[i].next) if(table[i].to!=from) { f[table[i].to]+=2; g[table[i].to]=max(g[table[i].to]+1,f[table[i].to]); stack[++top]=table[i].to; } sort(stack+1,stack+top+1,Compare); g[x]=a[x]; for(i=1;i<=top;i++) { g[x]=max(g[x],f[x]+g[stack[i]]); f[x]+=f[stack[i]]; } } int main() { int i,x,y; cin>>n; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i