树 题解

建议降紫

GDKOI2023 树 题解

二进制运算求和，首先考虑拆位。

问题变成对每个 d 求 u 子树 k 层内：

• $bit(x,y)$ 表示 $x$ 的二进制第 $y$ 位。

考虑链怎么做。为方便，容斥一下变成算后者的 0 个数减去 1 个数。

考虑在链上怎么做。这是经典问题。

发现 bit(x-l,d)=1 的 x 的位置是从 l 开始，每隔 2^d 个 0 有 2^d 个 1 。

我们显然可以对这个东西记一个前缀和。

具体的，f_i 从 f_{i+2^{d+1}} 转移，并附带 [i+2^d,2+2^{d+1}) 的系数和。

询问时找到最近的 l+2^{d+1} 的位置，一些边角位置都是好算的。

现在上树。发现只和深度有关，上个长剖即可。

注意长剖维护前缀和的方向。

同时这个做法注意卡常。不建议开 vector ，也不要傻乎乎的做 \log 次 dfs 。

#include<bits/stdc++.h>
#define bit(s,x) (((s)>>(x))&1)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
inline int read(){
    int x=0,c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}
const int N=1e6+3;
int n,Q,a[N],md[N],son[N],dfn[N],tim,idfn[N];
int f[N],g[N],h[N];
ll ans[N];
int m,mm;
int head[N],nxt[N];
inline void dfs1(int u){
    md[u]=0;
    for(int v=head[u];v;v=nxt[v]){
        dfs1(v);
        md[u]=max(md[u],md[v]+1);
        if(!son[u]||md[v]>md[son[u]])son[u]=v;
    }
}
inline void dfs2(int u){
    idfn[dfn[u]=++tim]=u;
    if(son[u])dfs2(son[u]);
    for(int v=head[u];v;v=nxt[v])if(v!=son[u])dfs2(v);
}
struct Node{int k,x,id;}b[N];
int main(){
    n=read();rep(i,1,n)a[i]=read();
    rep(i,2,n){
        int x=read();
        nxt[i]=head[x],head[x]=i;
    }
    Q=read();
    rep(i,1,Q)b[i].x=read(),b[i].k=read(),b[i].id=i;
    dfs1(1); dfs2(1);
    sort(b+1,b+Q+1,[&](Node A,Node B){return dfn[A.x]>dfn[B.x];});
    rep(d,0,29){
        m=1<<d,mm=1<<d+1;
        int p=1;
        per(i,n,1){
            int u=idfn[i];
            for(int v=head[u];v;v=nxt[v])if(v!=son[u]){
                rep(i,dfn[v],dfn[v]+md[v]){
                    int j=i-dfn[v]+dfn[u]+1;
                    f[j]+=f[i],g[j]+=g[i],h[j]+=h[i];
                }
            }
            h[i]=bit(a[u],d);
            f[i]=h[i]?-1:1;
            g[i]=0;
            if(md[u])f[i]+=f[i+1],h[i]+=h[i+1];
            if(md[u]>=mm)g[i]=g[i+mm]-f[i+mm];
            if(md[u]>=m)g[i]+=f[i+m];
            for(;p<=Q&&b[p].x==u;++p){
                int k=min(b[p].k,md[u]),k1=k&~((m<<1)-1);
                int res=g[i]-g[i+k1];
                k1+=m;
                if(k1<=k){
                    res+=f[i+k1];
                    if(k<md[u])res-=f[i+k+1];
                }
                res += h[i];
                if(k<md[u])res-=h[i+k+1];
                ans[b[p].id]+=1ll*res*m;
            }
        }
    }
    rep(i,1,Q)printf("%lld\n",ans[i]);
    return 0;
}