GYM D - Beauty and The Tree Gym - 101864D（启发式合并）

42 阅读 0 评论 28 点赞

我是靠谱客的博主欣慰招牌，最近开发中收集的这篇文章主要介绍GYM D - Beauty and The Tree Gym - 101864D（启发式合并），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：
一棵树，每层深度的值为这层深度所有节点权值和。
求删掉 $i$ 节点对应子树后的最大深度值。

思路：
裸的启发式合并。
先递归轻子树并清空，再递归重子树并且不清空，再遍历轻子树统计结果。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
vector<int>G[maxn];
int a[maxn],sum[maxn],DEP;
struct Tree {
    int l,r;
    int mx;
    int lazy;
}t[maxn << 2];
void pushup(int i) {
    t[i].mx = max(t[i * 2].mx,t[i * 2 + 1].mx);
}
void build(int i,int l,int r) {
    t[i].l = l;t[i].r = r;
    t[i].mx = t[i].lazy = 0;
    if(l == r) {
        t[i].mx = sum[l];
        return;
    }
    int m = (l + r) >> 1;
    build(i * 2,l,m);
    build(i * 2 + 1,m + 1,r);
    pushup(i);
}
void update(int i,int x,int v) {
    if(t[i].l == t[i].r) {
        t[i].mx += v;
        return;
    }
    int m = (t[i].l + t[i].r) >> 1;
    if(x <= m) update(i * 2,x,v);
    if(x > m) update(i * 2 + 1,x,v);
    pushup(i);
}
int d[maxn],son[maxn],siz[maxn],ans[maxn],SON;
void dfs(int x) {
    siz[x] = 1;
    sum[d[x]] += a[x];
    DEP = max(DEP,d[x]);
    for(int i = 0;i < G[x].size();i++) {
        int v = G[x][i];
        d[v] = d[x] + 1;
        dfs(v);
        siz[x] += siz[v];
        if(siz[v] > siz[son[x]]) {
            son[x] = v;
        }
    }
}
void add(int x,int val) {
    update(1,d[x],a[x] * val);
    for(int i = 0;i < G[x].size();i++) {
        int v = G[x][i];
        if(v == SON) continue;
        add(v,val);
    }
}
void solve(int x,int sta) {
    for(int i = 0;i < G[x].size();i++) {
        int v = G[x][i];
        if(v == son[x]) continue;
        solve(v,1);
    }
    if(son[x]) {
        solve(son[x],0);
        SON = son[x];
    }
    add(x,-1);
    SON = 0;
    ans[x] = t[1].mx;

    if(sta == 1) {
        add(x,1);
    }
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        int n;scanf("%d",&n);
        for(int i = 1;i <= n;i++) {
            G[i].clear();
            son[i] = 0;
            sum[i] = 0;
        }
        for(int i = 1;i <= n;i++) {
            scanf("%d",&a[i]);
        }
        for(int i = 2;i <= n;i++) {
            int x;scanf("%d",&x);
            G[x].push_back(i);
        }
        d[1] = 1;
        dfs(1);
        build(1,1,DEP);
        solve(1,1);
        for(int i = 2;i <= n;i++) {
            printf("%dn",ans[i]);
        }
    }
    return 0;
}