MR.Wen and his m***********g data

· · 题解

另类 O(n\log n)，，，

泛化一下 val_u=F(deg_u)，u 的“半邻域”是一个 u 是最浅点的连通块，反过来是 x 的祖先的深度在 d_x\sim dep_x 部分的点的“半邻域”包含 x。

要枚举题目式子中 u。对原树启发式合并。若继承重儿子，暴力加入轻儿子贡献，不考虑轻儿子的 u 的话，只需线段树维护每个 dep 的答案，具体而言是要维护两个数组 A,B，操作是 \forall A_i\gets A_i+B_i，\forall i\in [l,n],B_i\gets B_i\times v 和全部清空。当然可以 O(n\log^2 n)。然而本题的特殊性质有

v\in son(u)\Rightarrow d_v\le d_u+2

因此修改的 l（从轻子树来的）实可以看为 n 个连续的区间，运用线段树 k 连续叶子节点的虚树是 O(k+\log n) 的结论，精细实现获得 O(n\log n)。

对于轻儿子的 u 贡献：我撤走轻儿子 v 线段树的时候不去清空所有，而是加一个 tag 表示 1\sim dep_v 的部分保留其 A，这样留下了贡献，复杂度不变 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
bool mst;
const int maxn=1e6+5,mod=994007158;
vector<int> e[maxn];
int sze[maxn],son[maxn],n,F[maxn],deg[maxn],val[maxn],fa[maxn],res[maxn],D[maxn],d[maxn],dep[maxn];
void dfs(int u){
    sze[u]=1;if(e[u].empty())D[u]=0;else D[u]=n+1;
    dep[u]=dep[fa[u]]+1;
    for(auto v:e[u]){
        dfs(v);sze[u]+=sze[v];
        if(sze[v]>sze[son[u]])son[u]=v;
        D[u]=min(D[u],D[v]+1);
    }
}
void dfs2(int u){
    if(fa[u])D[u]=min(D[u],D[fa[u]]);
    d[u]=max(1,dep[u]-D[u]);
    for(auto v:e[u])dfs2(v);
}
vector<int> pt;
void qsy(int u){
    pt.push_back(u);
    for(auto v:e[u])qsy(v);
}
int pv[maxn],nd=0;
#define ls (k<<1)
#define rs (k<<1|1)
#define mid ((l+r)>>1) 
namespace ST{
    int mul[maxn<<2],add[maxn<<2],va[maxn<<2],st[maxn<<2],st2[maxn<<2],leaf[maxn<<2];
    inline void SET(int k){st[k]=1,mul[k]=1,add[k]=va[k]=0;}
    inline void ADD(int k,int v){(add[k]+=1ll*mul[k]*v%mod)%=mod;(va[k]+=1ll*mul[k]*v%mod)%=mod;}
    inline void MUL(int k,int x){mul[k]=1ll*mul[k]*x%mod;}
    inline void SET2(int k){st2[k]=1;}
    inline void check(int k){
        if(st2[k]){
            if(!leaf[k]){
                if(add[k])ADD(ls,add[k]),ADD(rs,add[k]),add[k]=0;
                if(mul[k]!=1)MUL(ls,mul[k]),MUL(rs,mul[k]),mul[k]=1;
                st2[ls]=1,st2[rs]=1;
            }else mul[k]=1,add[k]=0;
            st2[k]=0;
        }
    }
    inline void pushdown(int k){
        check(ls),check(rs);
        if(st[k])SET(ls),SET(rs),st[k]=0;
        if(add[k])ADD(ls,add[k]),ADD(rs,add[k]),add[k]=0;
        if(mul[k]!=1)MUL(ls,mul[k]),MUL(rs,mul[k]),mul[k]=1;
    }
    void build(int k,int l,int r){
        add[k]=0;
        if(l==r)return leaf[k]=1,void();
        build(ls,l,mid);build(rs,mid+1,r);
    }
    void predo(int k,int l,int r,int L,int R){
        check(k);
        if(l==r)return MUL(k,pv[l]);
        pushdown(k);
        if(L<=mid)predo(ls,l,mid,L,R);
        if(mid<R)predo(rs,mid+1,r,L,R);
    }
    void modify(int k,int l,int r,int x,int y,int v){
        check(k);
        if(x<=l&&r<=y)return MUL(k,v);
        pushdown(k);
        if(x<=mid)modify(ls,l,mid,x,y,v);
        if(mid<y)modify(rs,mid+1,r,x,y,v); 
    }
    void modify2(int k,int l,int r,int x,int y){
        check(k);
        if(x<=l&&r<=y)return ADD(k,1);
        pushdown(k);
        if(x<=mid)modify2(ls,l,mid,x,y);
        if(mid<y)modify2(rs,mid+1,r,x,y);
    }
    void modify3(int k,int l,int r,int x,int y){
        check(k);
        if(x<=l&&r<=y)return SET(k);
        pushdown(k);
        if(x<=mid)modify3(ls,l,mid,x,y);
        if(mid<y)modify3(rs,mid+1,r,x,y);
    }
    void modify4(int k,int l,int r,int x,int y){
        check(k);
        if(x<=l&&r<=y)return SET2(k);
        pushdown(k);
        if(x<=mid)modify4(ls,l,mid,x,y);
        if(mid<y)modify4(rs,mid+1,r,x,y);
    }
    int query(int k,int l,int r,int x){
        check(k);
        if(l==r)return va[k];
        pushdown(k);
        if(x<=mid)return query(ls,l,mid,x);
        else return query(rs,mid+1,r,x);
    }
}
using namespace ST;
void solve(int u){
    for(auto v:e[u]){
        if(v==son[u])continue;
        solve(v);modify3(1,1,nd,dep[v],nd);modify4(1,1,nd,1,dep[v]-1);
    }
    if(son[u])solve(son[u]);
    pt={u};for(auto v:e[u])if(v!=son[u])qsy(v);
    int L=n+1,R=0;for(auto x:pt)L=min(L,d[x]),R=max(R,d[x]);
    for(int i=L;i<=R;i++)pv[i]=1;
    for(auto x:pt)pv[d[x]]=1ll*pv[d[x]]*val[x]%mod;
    for(int i=L+1;i<=R;i++)pv[i]=1ll*pv[i-1]*pv[i]%mod;
    predo(1,1,nd,L,R);
    if(R+1<=n)modify(1,1,nd,R+1,nd,pv[R]);
    modify2(1,1,nd,d[u],nd);
    res[u]=query(1,1,nd,dep[u]);
}
bool med;
namespace Fastio {
    #define USE_FASTIO 1

    #define IN_LEN 45000

    #define OUT_LEN 45000

    char ch, c; int len;
    short f, top, s;
    inline char Getchar() {
        static char buf[IN_LEN], *l = buf, *r = buf;
        if (l == r) r = (l = buf) + fread(buf, 1, IN_LEN, stdin);
        return (l == r) ? EOF : *l++;
    }
    char obuf[OUT_LEN], *ooh = obuf;
    inline void Putchar(char c) {
        if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
        *ooh++ = c;
    }
    inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

    #undef IN_LEN
    #undef OUT_LEN
    struct Reader {
        template <typename T> Reader& operator >> (T &x) {
            x = 0, f = 1, c = Getchar();
            while (!isdigit(c)) { if (c == '-') f *= -1; c = Getchar(); }
            while ( isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = Getchar();
            x *= f;
            return *this;
        }

        Reader() {}
    } cin;
    const char endl = '\n';
    struct Writer {
        typedef long long mxdouble;
        template <typename T> Writer& operator << (T x) {
            if (x == 0) { Putchar('0'); return *this; }
            if (x < 0) Putchar('-'), x = -x;
            static short sta[40];
            top = 0;
            while (x > 0) sta[++top] = x % 10, x /= 10;
            while (top > 0) Putchar(sta[top] + '0'), top--;
            return *this;
        }
        Writer& operator << (const char *str) {
            int cur = 0;
            while (str[cur]) Putchar(str[cur++]);
            return *this;
        }
        inline Writer& operator << (char c) {Putchar(c); return *this;}
        Writer() {}
        ~ Writer () {flush();}
    } cout;
    #define cin Fastio::cin
    #define cout Fastio::cout
    #define endl Fastio::endl
}
signed main(){
    cin>>n;for(int i=2;i<=n;i++)cin>>fa[i],e[fa[i]].push_back(i),deg[i]++,deg[fa[i]]++;
    F[1]=F[2]=1;for(int i=3;i<=n;i++)F[i]=(F[i-1]+F[i-2])%mod;for(int i=1;i<=n;i++)val[i]=F[deg[i]];
    dfs(1);dfs2(1);for(int i=0;i<(maxn<<2);i++)mul[i]=1;for(int i=1;i<=n;i++)nd=max(nd,dep[i]);
    build(1,1,nd);solve(1);
    int ans=0;for(int i=1;i<=n;i++)ans^=res[i];
    cout<<ans<<endl;
    return 0;
}