题解：P10121 『STA - R4』保险丝

· · 题解

考场上花大部分时间搓了个 LCT 做法，然后被卡常了，不过在洛谷上直接过了，不知道是数据还是机子的缘故。

这是个不需要斐波那契数列性质的单 \log 做法，但似乎有巨大常数。

这个做法还是挺套路的，感觉基本上每一步都有迹可循。

考察半邻域的性质。

我们面对一个东西，可以想象形态/数学建模表达。

想象一下，一个直观的理解是从点 u 处往下倒一桶蜂蜜，蜂蜜流到一些地方就流不动了，流经的地方就是 u 的半邻域。

首先注意到一个点到根的路径上的点到叶子的最小距离，只需要对路径上每个点考虑其子树中的叶子，否则会走多余的路。

那么先对每个点处理出其子树中叶子到它的最短距离 dis_u，再对每个点求出其到根的路径上 dis 的最小值，记为 mn_u。

再考虑子树中一个点到子树根的距离，显然可以用深度直接算出。于是我们将涉及到的所有距离都转化为绝对的值相运算的结果，将相对距离写成绝对的深度，得到邻域的新定义：

如果用 DFS 序编号，一个半邻域就是二维平面上一个 3-side 矩形。

我们将半邻域转成矩形后仍然不好处理。考虑利用矩形只有 1 个 side 的那一维做扫描线，另一维是子树区间，性质比一般的区间好，考虑在树上做。

这样扫描线将静态问题转化为动态问题，实现了降维。

接下来考察询问的性质。

首先考虑询问范围的结构。不管扫描线那一维（半邻域）的限制（dep_v-mn_v\leq dep_u，它被扫描线的过程满足了）就是子树的子树，于是我们要平衡修改和查询。

于是我们要在扫描线的过程中，实现到根链的乘法、子树求和。

使用树链剖分+线段树是容易的。为了追求单 \log，可以采用 LCT，对于子树信息，维护一个点的虚子树信息和 Splay 子树里所有点的虚子树信息和。

一些细节：

考场代码，有点脏乱差。

#include <bits/stdc++.h>
#define gc getchar
using namespace std;
int rd() {
    int x = 0, f = 1; char c = gc();
    while(c < '0' || c > '9') { if(c == '-') f = (- 1); c = gc(); }
    while(c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return (x * f);
}
const int Mod = 994007158;
const int N = 1000000;
inline int Add(int x, int y) { return x + y >= Mod ? x + y - Mod : x + y; }
inline int Sub(int x, int y) { return x < y ? x + Mod - y : x - y; }
namespace BIT {
    int sum[N + 1];
    void add(int n, int p, int val) { for(; p <= n; p += (p & -p)) sum[p] += val; }
    int qry(int p) { int res = 0; for(; p >= 1; p -= (p & -p)) res += sum[p]; return res; }
}
namespace LCT {
    int fa[N + 1], ch[N + 1][2], val[N + 1], sum[N + 1], mul[N + 1], vir[N + 1], virsum[N + 1];
    void Init(int n, int pa[], int siz[]) { for(int u = 1; u <= n; ++ u) fa[u] = pa[u], val[u] = sum[u] = mul[u] = 1, vir[u] = virsum[u] = siz[u] - 1; } // ? ?
    inline void Up(int u) {
        sum[u] = Add(Add(sum[ch[u][0]], sum[ch[u][1]]), val[u]);
        virsum[u] = Add(Add(virsum[ch[u][0]], virsum[ch[u][1]]), vir[u]);
    } // sum[0] == 0 // 1ll // val
    inline void Mo(int u, int Mul) { val[u] = 1ll * val[u] * Mul % Mod; sum[u] = 1ll * sum[u] * Mul % Mod; mul[u] = 1ll * mul[u] * Mul % Mod; } // val
    void Dn(int u) { if(mul[u] > 1) { if(ch[u][0]) Mo(ch[u][0], mul[u]); if(ch[u][1]) Mo(ch[u][1], mul[u]); mul[u] = 1; } }
    inline int IsRt(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; }
    inline int Wh(int u) { return ch[fa[u]][1] == u; }
    void DnAll(int u) { if(! IsRt(u)) DnAll(fa[u]); Dn(u); }
    void Rot(int u) {
        int v, w, wu, wv; v = fa[u]; w = fa[v]; wu = Wh(u); wv = Wh(v);
        if(! IsRt(v)) ch[w][wv] = u; fa[u] = w; // 无论实虚信息都不用给 w 更新，因为从树和重链的角度看结构都没变
        fa[v] = u; ch[v][wu] = ch[u][wu ^ 1]; fa[ch[u][wu ^ 1]] = v; ch[u][wu ^ 1] = v;
        Up(v); Up(u);
    }
    void Splay(int u) { DnAll(u); while(! IsRt(u)) { if(! IsRt(fa[u])) Rot(Wh(u) == Wh(fa[u]) ? fa[u] : u); Rot(u); } } // ?
    void Access(int u) {
        for(int x = u, y = 0; x; x = fa[x]) {
            Splay(x);
            vir[x] = Add(Add(vir[x], virsum[ch[x][1]]), sum[ch[x][1]]);
            ch[x][1] = y;
            vir[x] = Sub(Sub(vir[x], virsum[y]), sum[y]);
            Up(x); y = x;
        }
    } // ? // x, not u
    void Mdf(int u, int Val) { Access(u); Splay(u); Mo(u, Val); } // Splay
    int Qry(int u) { Access(u); return Add(vir[u], val[u]); }
}
int n, F[N + 1], deg[N + 1], fa[N + 1], siz[N + 1], dep[N + 1], dis[N + 1], mn[N + 1], ans[N + 1];
vector < vector < int > > g(N + 1);
int lp[N + 1], rp[N + 1], tot;
struct Opt {
    int u, op;
    Opt(): u(0), op(0){}
    Opt(int U, int Op): u(U), op(Op){} // ?
}opt[2 * N + 1];
inline int Cmp(Opt x, Opt y) { // ?
    int p = (x.op == 1 ? dep[x.u] : dep[x.u] - mn[x.u]);
    int q = (y.op == 1 ? dep[y.u] : dep[y.u] - mn[y.u]);
    if(p != q) return p < q;
    return x.op < y.op;
}
void dfs(int u) {
    lp[u] = ++ tot;
    dep[u] = dep[fa[u]] + 1;
    siz[u] = 1;
    if(u > 1 && deg[u] == 1) dis[u] = 0; // n >= 2，所以根一定不是叶子（存疑）
    else dis[u] = n + 1;
    for(int v : g[u]) {
        dfs(v);
        siz[u] += siz[v];
        dis[u] = min(dis[u], dis[v] + 1);
    }
    rp[u] = tot;
}
void Solve() {
    n = rd();
    F[1] = F[2] = 1; for(int i = 3; i <= n; ++ i) F[i] = Add(F[i - 1], F[i - 2]); // N >= 2
    for(int i = 2; i <= n; ++ i) {
        fa[i] = rd();
        ++ deg[i]; ++ deg[fa[i]];
        g[fa[i]].emplace_back(i);
    }
    dfs(1);
    for(int u = 1; u <= n; ++ u) {
        mn[u] = dis[u];
        if(u > 1) mn[u] = min(mn[u], mn[fa[u]]);
    }
    LCT::Init(n, fa, siz);
    int cnt = 0;
    for(int u = 1; u <= n; ++ u) {
        ++ cnt; opt[cnt] = Opt(u, 0);
        ++ cnt; opt[cnt] = Opt(u, 1);
    }
    sort(opt + 1, opt + 2 * n + 1, Cmp);

//  vector < bool > vis(n + 1);

    for(int i = 1; i <= 2 * n; ++ i) {
        if(opt[i].op == 0) {
            LCT::Mdf(opt[i].u, F[deg[opt[i].u]]);
//          vis[opt[i].u] = true;
            BIT::add(n, lp[opt[i].u], 1); // lp[ ]
        } else {
            int res = (LCT::Qry(opt[i].u));
//          ans[opt[i].u] = (BIT::qry(rp[opt[i].u])) - (BIT::qry(lp[opt[i].u] - 1));
//          ans[opt[i].u] = siz[opt[i].u];
            ans[opt[i].u] = (res + (BIT::qry(rp[opt[i].u])) - (BIT::qry(lp[opt[i].u] - 1)) - siz[opt[i].u]) % Mod; // siz[opt[i].u], not n
//          cout << "u = " << opt[i].u << " \n";
//          cout << "exist: ";for(int v = 1; v <= n; ++ v) if(vis[v]) cout << v << " ";
//          cout << "\n";
        }
    }
    int res = 0;
    for(int u = 1; u <= n; ++ u) res = (res ^ ((ans[u] + Mod) % Mod));
    printf("%d\n", res);

//  for(int u = 1; u <= n; ++ u) cout << ans[u] << ' ';
//  cout << "\n";
}
int main() {
//  freopen("9.in", "r", stdin);
    freopen("fuse.in", "r", stdin);
    freopen("fuse.out", "w", stdout);
    Solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

2025.5.22