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

· · 题解

题解

暴力出奇迹。

发现这个要求的东西很奇葩，我们的式子里面带了一个斐波那契数列，并且当一个点度数 \le2 的时候都是 1，再观察特殊性质，其中性质 C 保证树中除根以外每个节点的度数均 \ge3，好奇怪啊这啥意思呢？就是说这棵树是满二叉树，我们如果暴力去计算其实复杂度是调和级数 O(n\log n) 的。这很优美不是吗？但是事情并非我们所愿，现在树上还有一些地方是一条长链，如果暴力做就会被卡炸。怎么办？考虑贡献是如何计算的，我们会将子树的度数套上斐波那契数列乘起来。所以我们就可以折叠长链。具体的我们可以记录一个点往下跳到第一个不是长链上的位置，如果这个点度数大于 2 就是他自己。然后暴力 dfs 的时候我们先判断这个点的度数是不是小于 2 的，如果是我们就进行跳跃，注意在跳的时候判断能不能跳完整个链。然后其他就直接做即可。

代码

/*
 * @Author: Nekopedia 
 * @Date: 2025-05-22 10:35:18 
 * @Last Modified by: Nekopedia
 * @Last Modified time: 2025-05-22 19:29:36
 */
#include <bits/stdc++.h>
#define ll long long
#define gc() (p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
const int N = 1e6 + 5, S = 1 << 25, p = 994007158, inf = 2e9;
const ll INF = 2e18;
char buf[S], *p1, *p2;
inline ll rd(){
    ll x = 0, f = 1; char c = gc();
    while(! isdigit(c)){if(c == '-')f = - f; c = gc();}
    while(isdigit(c)){x = (x << 3) + (x << 1) + (c ^ 48); c = gc();}
    return x * f;
}
void fileio(const string &s){
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

inline int Add(int x, int y){return x - p + y >= 0 ? x - p + y : x + y;}
inline int Sub(int x, int y){return x < y ? x - y + p : x - y;}
inline int Mul(int x, int y){return 1ll * x * y % p;}
inline int Mo(ll x){return (x % p + p) % p;}
inline int qmi(int x, int y){int res = 1; for(; y; y >>= 1, x = Mul(x, x))if(y & 1)res = Mul(res, x); return res;}
inline void exgcd(ll a, ll b, ll &x, ll &y){if(! b)return x = 1, y = 0, void(); exgcd(b, a % b, y, x); y -= a / b * x;}
inline int Inv(int q){ll x, y; exgcd(q, p, x, y); return Mo(x);}

int n, a[N], fa[N], mi[N], prmi[N], deg[N], son[N], jp[N], dep[N];
int fib[N], ans, res;
vector < int > g[N];

void dfs1(int u){
    mi[u] = inf; dep[u] = dep[fa[u]] + 1;
    for(int v : g[u])dfs1(v), mi[u] = min(mi[u], mi[v]), jp[u] = jp[v];
    ++mi[u]; if(! son[u])mi[u] = 0; if(son[u] > 1)jp[u] = u;
}
void dfs2(int u){
    prmi[u] = (u == 1 ? mi[u] : min(prmi[fa[u]], mi[u]));
    for(int v : g[u])dfs2(v);
}
int dfs3(int st, int u){
    if(dep[u] - dep[st] > prmi[u])return 1;
    if(son[u] <= 1){
        int lim = min(dep[st] + prmi[u], mi[u] + dep[st] + dep[u] >> 1);
        if(jp[u] and lim >= dep[jp[u]]){
            int tmp = dfs3(st, jp[u]);
            res = Add(res, Mul(dep[jp[u]] - dep[u], tmp));
            return tmp;
        }
        res = Add(res, min(mi[u] + 1, lim - dep[u] + 1));
        return 1;
    }
    int tmp = fib[deg[u]];
    for(int v : g[u])tmp = Mul(tmp, dfs3(st, v));
    res = Add(res, tmp); return tmp;
}

const string FileName = "fuse";
signed main(){
    fileio(FileName);
    n = rd(); for(int i = 2; i <= n; ++i){
        g[fa[i] = rd()].push_back(i);
        ++deg[fa[i]]; ++deg[i]; ++son[fa[i]];
    }
    fib[1] = fib[2] = 1; for(int i = 3; i <= n; ++i)fib[i] = Add(fib[i - 1], fib[i - 2]);
    dfs1(1); dfs2(1);
    for(int i = 1; i <= n; ++i, res = 0)dfs3(i, i), ans ^= res; cout << ans;
    return 0;
}