很明显,题意描述的是一个仙人掌图。

考虑建圆方树。

那么询问可以转化为$x$的子树。

之后通过$dfs$序改变成区间$[l,r]$

那么题意就变成了询问区间$[l,r]$中程度$\le y$的品尝次数或奇或偶的种类个数

套上一个莫队+值域分块即可勉强解决此题。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define fin(s) freopen(s".in","r",stdin)
#define I inline 
using namespace std;
const int N=2e5+5,M=N<<1;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int arr[N],tim,n,m,bl[N],blv[N],Q;
struct Query
{
    int l,r,id,v,op;
    bool operator <(const Query a)const{return bl[l]==bl[a.l]?r<a.r:bl[l]<bl[a.l];}
}q[M];    
I int get(int d)
{
    int l=1,r=tim;
    for(int mid=l+r>>1;l<r;mid=l+r>>1)
        if(arr[mid]<d)l=mid+1;
        else r=mid;
    return l;
}
namespace Block
{
    int c[N],v[N],s[N][2],T,Tv,ans[N],sr,srv;
    I void add(int x)
    {
        if(!c[x])++s[blv[x]][1];
        else if(c[x]&1)--s[blv[x]][1],++s[blv[x]][0];
        else --s[blv[x]][0],++s[blv[x]][1];
        ++c[x];
    }
    I void del(int x)
    {
        if(c[x]==1)--s[blv[x]][1];
        else if(c[x]&1)--s[blv[x]][1],++s[blv[x]][0];
        else --s[blv[x]][0],++s[blv[x]][1];
        --c[x];
    }
    I int cal(int x,int op)
    {
        int w=0,p=blv[x];
        for(int i=1;i<p;i++)w+=s[i][op];
        for(int i=(p-1)*srv+1;i<=x;i++)
            if(c[i]&&(c[i]&1)==op)++w;
        return w;
    }
    void init()
    {
        sr=sqrt(n),srv=sqrt(tim);
        T=(n-1)/sr+1,Tv=(tim-1)/srv+1;
        for(int i=1,L=1,R=sr;i<=T;i++,L=R+1,R=min(R+sr,n))for(int j=L;j<=R;j++)bl[j]=i;
        for(int i=1,L=1,R=srv;i<=Tv;i++,L=R+1,R=min(R+srv,tim))for(int j=L;j<=R;j++)blv[j]=i;
        sort(q+1,q+Q+1);
        int l=1,r=0;
        for(int i=1;i<=Q;i++)
        {
            while(l>q[i].l)add(v[--l]);
            while(r<q[i].r)add(v[++r]);
            while(l<q[i].l)del(v[l++]);
            while(r>q[i].r)del(v[r--]);
            int p=get(q[i].v);
            if(arr[p]>q[i].v)p--; 
            ans[q[i].id]=cal(p,q[i].op);
        }
        for(int i=1;i<=Q;i++)
            qw(ans[i]),puts("");
    }
}
int cnt,val[N];
namespace Cactus
{
    struct edge{int y,next;}a[M<<1];int len,last[M];
    void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
    int dfn[M],ed[M],num;
    void dfs(int x,int fa)
    {
        if(x<=n)dfn[x]=++num;else dfn[x]=-1;
        for(int k=last[x],y;k;k=a[k].next)
            if((y=a[k].y)!=fa)dfs(y,x);
        if(x<=n)ed[x]=num;
    }
    void init()
    {
        dfs(1,0);
        for(int i=1;i<=n;i++)Block::v[dfn[i]]=val[i];
        qr(Q);
        for(int i=1;i<=Q;i++)
        {
            int ty,x,y;qr(ty),qr(x),qr(y);
            q[i]=(Query){dfn[x],ed[x],i,y,ty};
        }
    }
}
namespace Tarjan
{
    struct edge{int y,next;}a[N<<1];int len,last[N];
    void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
    int dfn[N],low[N],sta[N],tp,num;
    void tarjan(int x)
    {
        dfn[x]=low[x]=++num;sta[++tp]=x;
        for(int k=last[x],y;k;k=a[k].next)
        {
            if(!dfn[y=a[k].y])
            {
                tarjan(y);
                low[x]=min(low[x],low[y]);
                if(dfn[x]==low[y])
                {
                    int z;++cnt;
                    do{
                        z=sta[tp--];
                        Cactus::ins(z,cnt);
                        Cactus::ins(cnt,z);
                    }while(z!=y);
                    Cactus::ins(x,cnt);
                    Cactus::ins(cnt,x);
                }
            }
            else low[x]=min(low[x],dfn[y]);
        }
    }
    void init()
    {
        qr(n),qr(m);
        for(int i=1;i<=n;i++)qr(val[i]),arr[i]=val[i];
        sort(arr+1,arr+n+1);tim=0;
        for(int i=1;i<=n;i++)
            if(i==1||arr[i]!=arr[i-1])arr[++tim]=arr[i];
        for(int i=1;i<=n;i++)val[i]=get(val[i]);
        for(int i=1,x,y;i<=m;i++)qr(x),qr(y),ins(x,y),ins(y,x);
        cnt=n;tarjan(1);
    }
}
int main()
{
    Tarjan::init();
    Cactus::init();
    Block::init();
    return 0;
}