题目大意：给定一棵树，从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 <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 500500using 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<n;i++){scanf("%d%d",&x,&y);Add(x,y);Add(y,x);}Tree_DP(1,0);cout<<max(g[1],f[1]+a[1])<<endl;return 0;}
只有不快的斧，没有劈不开的柴。
