bzoj3829 POI2014 FAR-FarmCraft

题目链接

思路

用\(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;
}