洛谷P8968 觅光 | Searching for Hope (hard version) 题解

题目链接：洛谷P8968 觅光 | Searching for Hope (hard version)

题意：

现在有一棵 \(n\) 个节点的有根二叉树。

凡人与神明在这棵树上进行一个游戏。凡人需要从根投下若干个球，每个球带 \(1\) 单位正电荷或带 \(1\) 单位负电荷。

树上每一个点有容量，第 \(i\) 个点可以容纳 \(c_i\) 个球。初始每一个点容纳的球数为 \(0\)。我们称一个点被充满当且仅当它容纳的球的个数等于它的容量。

每一次一个球下落到一个点时：

如果该点没有孩子节点或者所有孩子节点上都已经充满球，则停止，该点容纳的球的个数 \(+1\)；

如果该点恰有一个孩子节点未充满，则向那个孩子下落；

如果有 \(2\) 个孩子节点均未充满：

如果左侧子树中所有球的电荷代数和大于右侧子树所有球的电荷代数和，则如果当前球带正电则向右下落，否则向左下落；

如果左侧子树中所有球的电荷代数和小于右侧子树所有球的电荷代数和，则如果当前球带正电则向左下落，否则向右下落；

如果左侧子树中所有球的电荷代数和等于右侧子树所有球的电荷代数和，则由神明决定向哪个方向下落。

其中，电荷代数和指的是正电荷的数量减去负电荷的数量。

在游戏开始前，双方约定目标点 \(u\)。在一个回合中，凡人选择这次投下的球的电性，神明按上述规则控制球的下落过程。当 \(u\) 被充满时，游戏结束。

凡人希望游戏回合数尽量少，神明希望游戏回合数尽量多。假设双方足够聪明。

对所有：\(1\leq u\leq n\)，求游戏轮数 \(r_u\)。

输入格式：

第一行，一个正整数 \(n\)。

第二行，\(n-1\) 个整数 \(f_2, f_3, \ldots, f_n\)，其中 \(f_i\) 代表 \(i\) 的父亲的编号。

第三行，\(n\) 个整数 \(c_1, c_2, \ldots, c_n\)。

输出格式：

输出一行，\(n\) 个整数 \(r_1, r_2, \ldots, r_n\)。

数据范围：

简单版 \(n \le 10^3\) ，本题是困难版 \(n\le 10^6\) 。

本题最大 I/O 量达到 20 MiB，请注意 I/O 效率。

\(2 \le n \le {10}^6\)，满足树是以 \(1\) 为根的二叉树，\(1 \le f_i < i\)，\(1 \le c_i \le {10}^{12}\)。

考虑从 \(u\) 开始向上跳，设当前答案为 \(x\) ，另一棵子树的大小为 \(a\) ，则 \(x \gets x + \min\{x,a\}\)

这个操作的含义是，往当前点的兄弟所在子树丢正电荷，丢满 \(\min\{x,a\}\) 个，再丢就一定在 fa 上了。

简单版直接暴力模拟即可，因此考虑优化这个跳的过程。

把 \(\min\) 拆开可以发现 \(x \gets 2x(x < a),~x \gets x + a(x \ge a)\)

显然前者至多发生 \(\mathcal{O}(\log n)\) 次，故考虑单独处理后者。

我们需要找到最小的 \(p > i\) 满足 \[ x+\sum_{j=i+1}^{p-1} a_j<a_p \] 移个项可以得到 \[ a_p-\sum_{j=1}^{p-1} a_j>x-\sum_{j=1}^i a_j \] 左侧可以用线段树上二分解决，时间复杂度 \(\mathcal{O}(n \log^2 n)\)

不过这个我没写（懒），据说维护前缀和而非区间和可以小常数卡过去。

考虑进一步优化。容易发现，本题的倍增是一段一段的整体，于是利用一种类似于路径压缩的思想进行优化

最初每个点的父亲是自己，如果它一定不会触发父亲的翻倍，就把它和父亲压缩到一起

这样，每步都会跳到某段较长的一定不会触发翻倍的段的顶端（~~我怎么觉得更像树剖跳链啊~~）

具体地，我们维护每个点的「不触发倍增的极长段」的阈值 \(l\) ，段顶 \(t\) ，跳到顶端后需要加的值 \(a\)

每次加入一个新点，如果 \(l + a \ge l_t\) ，即不触发这个段的倍增就一定不会触发上面的段的倍增（废话）

那么其实就是这种情况直接与上面的段顶合并，然后重复这个合并的过程，直到 \(l + a < l_t\) 。

每经过这样的一个段，\(l\) 的值至少翻倍（ \(l + a \ge 2l\) ），所以最多经过 \(\mathcal{O}(\log n)\) 个这样的段

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]

int n,a[N],ans[N],fa[N],sz[N],ch[N][2];
struct node { int u,v,w; };
vector<node> q;
void dfs(int x)
{
    if(!x) return;
    int p = q.size() - 1, cnt = 0; ans[x] = sz[x];
    while(p > 0) {
        auto [u,v,w] = q[p]; ++cnt;
        if(ans[x] >= u) {
            ans[x] += v; p = w; continue;
        }
        ans[x] <<= 1; --p;
    }
    if(ls(x))
    {
        if(rs(x))
        {
            node t = {sz[rs(x)], sz[rs(x)], (int)q.size() - 1};
            while(t.u + t.v >= q[t.w].u) { t.v += q[t.w].v, t.w = q[t.w].w; }
            q.push_back(t);
        }
        dfs(ls(x)); if(rs(x)) q.pop_back();
    }
    if(rs(x))
    {
        if(ls(x))
        {
            node t = {sz[ls(x)], sz[ls(x)], (int)q.size() - 1};
            while(t.u + t.v >= q[t.w].u) { t.v += q[t.w].v, t.w = q[t.w].w; }
            q.push_back(t);
        }
        dfs(rs(x)); if(ls(x)) q.pop_back();
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        cin >> fa[i];
        (ls(fa[i]) ? rs(fa[i]) : ls(fa[i])) = i;
    }
    for(int i = 1; i <= n; i++) { cin >> a[i]; sz[i] = a[i]; }
    for(int i = n; i > 1; i--) sz[fa[i]] += sz[i];
    q.push_back({INF, 0, 0}); dfs(1);
    for(int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
    return 0;
}