題目鏈接

思路

用\(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("%d\n",max(f[1],(n - 1) * 2 + c[1]));
    return 0;
}