uoj418（树上相邻交换）

有些题里面很有用的贪心小技巧。

把过程倒过来：设根为 $i$，先在根上放 $w_i$ 个石子。然后每次选一个有石子的点 $u$，对于它的所有孩子 $v$，往 $v$ 上放 $w_v$ 个石子，然后移除 $u$ 上的石子。

对于 $u$，设 $s_u$ 为 $u$ 的所有孩子的 $w_u$ 的和。那么对 $u$ 进行操作就相当于将树上的石子数增加 $s_u$ 再减去 $w_u$。需要最小化树上的石子数的最大值。

如果可以按任意顺序进行操作，那么就是一个经典的贪心相邻交换。结论是：

1. 先操作 $s_u<w_u$ 的，再操作 $s_u\geq w_u$ 的。
2. $s_u<w_u$ 的按照 $s_u$ 升序。
3. $s_u\geq w_u$ 的按照 $w_u$ 降序。

但是现在有个树的限制，需要按树从上到下操作。

考虑到，对于 $u$ 和 $u$ 的一个孩子 $v$，如果 $u$ 会排在 $v$ 后面，那么一定是操作完 $u$ 立刻操作 $v$。所以可以把 $u,v$ 缩起来。

具体来说，对于每一个子树维护一个序列表示子树里面的操作顺序。合并的时候先启发式合并所有子树的序列。然后考虑根是不是比序列的开头更优，如果不是，将两者合并。重复直到根优于序列开头或序列为空，然后把根放进序列。

但是这题还需要对每一个子树求，所以得手写一个平衡树来维护这个序列的答案。总复杂度 $O(n\log^2 n)$。

#include <bits/stdc++.h>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 200005;

struct Vecc {
    long long x, y;
    Vecc() {}
    Vecc(long long x, long long y) : x(x), y(y) {}
    inline Vecc operator + (const Vecc& b) const {
        return Vecc(max(x, x - y + b.x), max(x, x - y + b.x) - (x - y + b.x - b.y));
    }
    inline bool operator < (const Vecc& b) const {
        if ((x - y < 0) != (b.x - b.y < 0)) return x - y < b.x - b.y;
        else if (x - y < 0) return x < b.x;
        else return y > b.y;
    }
};
#define Size(p) (p ? p->siz : 0)
#define Maxs(p) (p ? p->mxs : 0)
#define Sum(p) (p ? p->sum : 0)
struct Node {
    Vecc val;
    int siz, rdv;
    long long mxs, sum;
    Node *l, *r;
    inline void Update() {
        siz = Size(l) + Size(r) + 1;
        sum = Sum(l) + Sum(r) + val.x - val.y;
        mxs = max(max(Maxs(l), Sum(l) + val.x), Sum(l) + val.x - val.y + Maxs(r));
    }
};
Node nd[N << 1];
int top;
struct Fhqtreap {
    Node *_root;
    inline Node* New(Vecc val) {
        Node *p = &nd[++top];
        p->val = val;
        p->l = p->r = NULL;
        p->siz = 1;
        p->rdv = rnd();
        p->Update();
        return p;
    }
    inline void splitVal(Node *p, Vecc spk, Node *&lt, Node *&rt) {
        if (!p) {
            lt = rt = NULL;
            return;
        }
        if (p->val < spk) {
            lt = p;
            splitVal(p->r, spk, p->r, rt);
        } else {
            rt = p;
            splitVal(p->l, spk, lt, p->l);
        }
        p->Update();
    }
    inline Node* Merge(Node *lt, Node *rt) {
        if (!lt) return rt;
        if (!rt) return lt;
        if (lt->rdv > rt->rdv) {
            lt->r = Merge(lt->r, rt);
            lt->Update();
            return lt;
        } else {
            rt->l = Merge(lt, rt->l);
            rt->Update();
            return rt;
        }
    }
    inline void Ins(Node *p) {
        Node *p1, *p2;
        splitVal(_root, p->val, p1, p2);
        _root = Merge(Merge(p1, p), p2);
    }
    inline Node* Lmost() {
        Node *p = _root;
        while (p->l) p = p->l;
        return p;
    }
    inline void dfsRmv(Node *p) {
        if (p->l->l) dfsRmv(p->l);
        else p->l = p->l->r;
        p->Update();
    }
    inline void rmvL() {
        if (!(_root->l)) _root = _root->r;
        else dfsRmv(_root);
    }
    inline void Output(Node *p) {
        if (!p) return;
        Output(p->l);
        cout << p->val.x << "," << p->val.y << " ";
        Output(p->r);
    }
};

Fhqtreap tr[N];
vector <int> g[N];
long long w[N], ans[N];
Vecc vec[N];
int n, fa[N];

inline void Read() {
    n = qread();
    for (int i = 2;i <= n;i++) g[fa[i] = qread()].push_back(i);
    for (int i = 1;i <= n;i++) w[i] = qread();
}

inline void Prefix() {
    for (int i = 1;i <= n;i++) vec[i].y = w[i];
    for (int i = 2;i <= n;i++) vec[fa[i]].x += w[i];
}

inline void addTr(Node *p, int tid) {
    if (!p) return;
    addTr(p->l, tid); addTr(p->r, tid);
    p->l = NULL; p->r = NULL; p->Update();
    tr[tid].Ins(p);
}

inline void Dfs(int u) {
    tr[u]._root = NULL;
    for (int v : g[u]) {
        Dfs(v);
        if (Size(tr[v]._root) > Size(tr[u]._root)) swap(tr[u], tr[v]);
        addTr(tr[v]._root, u);
    }
    Node *p = tr[u].New(vec[u]);
    while (tr[u]._root) {
        Node *cur = tr[u].Lmost();
        if (cur->val < p->val) {
            p->val = p->val + cur->val;
            tr[u].rmvL();
        } else break;
    }
    p->Update();
    tr[u]._root = tr[u].Merge(p, tr[u]._root);
    //cout << u << ":"; tr[u].Output(tr[u]._root); cout << endl;
    ans[u] = w[u] + Maxs(tr[u]._root);
}

int main() {
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    qread();
    Read();
    Prefix();
    Dfs(1);
    for (int i = 1;i <= n;i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}