CF570D Tree Requests & CF246E Blood Cousins Return

妄图用莫队和线段树合并而不学dsu on tree中。。。

之所以加上“dsu on tree”的标签大概是因为我可能会失败

CF570D

CF246E

先看个简单的CF570D。

这里是没有dsu on tree的做法，而且跑的比$dsu\ on\ tree$快。

看子树中某个深度的点能不能重拍成回文，就是看出现奇数次的字符的个数是否小于等于一，首先这个才26个字母，可以状压一下。

然后就是想办法把树上问题转到序列的一个连续区间上，dfs序上子树内节点连续，bfs序上深度递增，所以我们必须有所取舍。然而bfs序的另一个性质就是深度相同的连续一段节点的dfs序也是递增的（显然，且不会证）。

所以就有一个在bfs序上找到x的子树内深度为y的节点的做法。先预处理好深度为y的一个区间，之后二分出这个区间里dfs序在$[dfn[x],dfn[x]+size[x]-1]$中的区间。这个区间里的点就是我们所要处理的点。

对于这题，状压一下每个字符的出现次数奇偶性，就可以随便判什么回文了。

稍微多一个莫队的CF246E。

把名字hash一下，把森林看成根为0的树，用上面的方法把区间找出来，就是一个数颜色了。偷懒写个莫队就是最优解，写个主席树肯定更快，最优解在等着你！！！

CF570D：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int next,to;
}w[500001];
int head[500001],tail,bfn[500001],val[500001],p[500001],n,num;
int deep[500001],heap,idx[500001],ed[500001],rf[500001],m,cnt;
char ch[500001];
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
void bfs(){
    heap=tail=1; bfn[tail]=1; deep[1]=1;
    while (heap<=tail){
        int x=bfn[heap]; p[heap]=idx[x]; rf[deep[x]]=heap;
        for (int i=head[x]; i; i=w[i].next){
            deep[w[i].to]=deep[x]+1;
            bfn[++tail]=w[i].to;
        }
        heap++;
    }
}
void dfs(int x){
    idx[x]=++num;
    for (int i=head[x]; i; i=w[i].next)
        dfs(w[i].to);
    ed[x]=num;
}
int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for (int i=2; i<=n; i++)
        scanf("%d",&x),add(x,i);
    dfs(1); bfs(); rf[deep[bfn[n]]+1]=n+1;
    // for (int i=1; i<=n; i++) printf("%d ",bfn[i]); puts("");
    // for (int i=1; i<=deep[bfn[n]]; i++) printf("%d ",rf[i]); puts("");
    scanf("%s",ch+1);
    for (int i=1; i<=n; i++){
        val[i]=(1<<(ch[bfn[i]]-'a'));
        val[i]^=val[i-1];
    }
    // for (int i=1; i<=n; i++) printf("%d ",val[i]); puts("");
    int l,r,u;
    for (int i=1; i<=m; i++){
        scanf("%d%d",&x,&y);
        if (y<deep[x]||y>deep[bfn[n]]){puts("Yes"); continue;}
        l=lower_bound(p+rf[y-1]+1,p+rf[y]+1,idx[x])-p;
        r=lower_bound(p+rf[y-1]+1,p+rf[y]+1,ed[x]+1)-p-1;
        // printf("%d %d %d %d\n",rf[y-1]+1,rf[y],idx[x],ed[x]+1);
        // printf("%d %d\n",l,r);
        if (l>r){puts("Yes"); continue;}
        u=val[r]^val[l-1];
        if ((u&(u-1))==0) puts("Yes");
        else puts("No");
    }
    return 0;
}

CF246E

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const ll bas=233,mod=19260817;
struct node{
    int next,to;
}w[500002];
struct ls{
    int h; ll z;
}b[500002];
struct que{
    int l,r,h;
}q[500002];
int head[500002],tail,bfn[500002],val[500002],p[500002],n,num;
int deep[500002],heap,idx[500002],ed[500002],rf[500002],m,cnt;
int a[500002],ans[500002],sum,o[500002],blo,bl[500002],c[500002];
char ch[500002];
inline bool cmp(ls c,ls d){return c.z<d.z;}
inline bool cmp2(que c,que d){
    if (bl[c.l]!=bl[d.l]) return c.l<d.l;
    if (bl[c.l]&1) return c.r<d.r;
    return c.r>d.r;
}
inline void add(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
void bfs(){
    heap=tail=1; bfn[tail]=0; deep[0]=0;
    while (heap<=tail){
        int x=bfn[heap]; p[heap]=idx[x]; rf[deep[x]]=heap;
        for (int i=head[x]; i; i=w[i].next){
            deep[w[i].to]=deep[x]+1;
            bfn[++tail]=w[i].to;
        }
        heap++;
    }
}
void dfs(int x){
    idx[x]=++num;
    for (int i=head[x]; i; i=w[i].next)
        dfs(w[i].to);
    ed[x]=num;
}
inline void bdd(int x){if (!o[c[x]]) sum++; o[c[x]]++;}
inline void del(int x){o[c[x]]--; if (!o[c[x]]) sum--;}
int main(){
    int x,y; ll z;
    scanf("%d",&n);
    for (int i=1; i<=n; i++){
        scanf("%s%d",ch+1,&y);
        x=strlen(ch+1); z=0; add(y,i);
        for (int j=1; j<=x; j++)
            z=(bas*z+ch[j]-'a'+1)%mod;
        b[i].z=z; b[i].h=i;
    }
    sort(b+1,b+n+1,cmp);
    for (int i=1; i<=n; i++){
        a[b[i].h]=a[b[i-1].h];
        if (b[i].z!=b[i-1].z) a[b[i].h]++;
    }
    dfs(0); bfs(); rf[deep[bfn[n+1]]+1]=n+2;
    scanf("%d",&m);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&x,&y); y+=deep[x];
        if (y<deep[x]||y>deep[bfn[n+1]]){q[i].h=0; continue;}
        q[i].l=lower_bound(p+rf[y-1]+1,p+rf[y]+1,idx[x])-p;
        q[i].r=lower_bound(p+rf[y-1]+1,p+rf[y]+1,ed[x]+1)-p-1;
        if (q[i].l>q[i].r){q[i].h=0; continue;} q[i].h=i;
    }
    blo=sqrt(n);
    for (int i=1; i<=n+1; i++){
        bl[i]=(i-1)/blo+1;
        c[i]=a[bfn[i]];
    }
    sort(q+1,q+m+1,cmp2);
    int l=1,r=0;
    for (int i=1; i<=m; i++){
        if (!q[i].h) continue;
        while (l<q[i].l) del(l),l++;
        while (l>q[i].l) l--,bdd(l);
        while (r>q[i].r) del(r),r--;
        while (r<q[i].r) r++,bdd(r);
        ans[q[i].h]=sum;
    }
    for (int i=1; i<=m; i++) printf("%d\n",ans[i]);
    return 0;
}