题目链接

思路

用(f[i])表示完成第(i)棵子树所需要得时间。
考虑如果有两个子树(a)和(b),如果先去完成子树(a)，那么对于花费得时间就是(f[b] + siz[a] times 2 + 1)
所以如果有先遍历(a)更优秀的话。那么一定有(f[b] + siz[a] times 2 + 1 le f[a] + siz[b] times 2+ 1)
即(f[a] – siz[a] times 2 le f[b] – siz[b] times 2)
所以对于当前节点的每个子树按照上面的方法排个序。然后统计一下答案即可。
有个坑点就是必须最后完成(1)号节点，所以最后不能直接输出(f[1])，好在从样例里可以发现(233)

代码

/* * @author: wxyww * @date:   2019-02-13 07:26:04 * @last modified time: 2019-02-13 09:13:20 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 500000 + 100; ll read() {     ll x=0,f=1;char c=getchar();     while(c<'0'||c>'9') {         if(c=='-') f=-1;         c=getchar();     }     while(c>='0'&&c<='9') {         x=x*10+c-'0';         c=getchar();     }     return x*f; } vector<int>e[n]; int f[n],siz[n]; int n,c[n]; bool cmp(int x,int y) {     return f[x] - siz[x] * 2 > f[y] - siz[y] * 2; } void dfs(int u,int father) {     int k = e[u].size();     siz[u] = 1;     int now = 0;     if(c[u] != 1)     f[u] = c[u];     for(int i = 0;i < k;++i) {         int v = e[u][i];         if(v == father) continue;         dfs(v,u);         siz[u] += siz[v];     }     sort(e[u].begin(),e[u].end(),cmp);     for(int i = 0;i < k;++i) {         int v = e[u][i];         if(v == father) continue;         f[u] = max(f[u],now * 2 + f[v] + 1);         now += siz[v];     } } int main() {     n = read();     for(int i = 1;i <= n;++i) c[i] = read();     for(int i = 1;i < n;++i) {         int u = read(),v = read();         e[u].push_back(v);e[v].push_back(u);     }     dfs(1,0);     printf("%dn",max(f[1],(n - 1) * 2 + c[1]));     return 0; }