欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj3829 POI2014 FAR-FarmCraft

程序员文章站 2022-05-25 19:45:20
思路 用$f[i]$表示完成第$i$棵子树所需要得时间。 考虑如果有两个子树$a$和$b$,如果先去完成子树$a$,那么对于花费得时间就是$f[b] + siz[a] \times 2 + 1$ ......

题目链接

思路

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