太妙了，甚至不用建出来圆方树！

题意：给你一个仙人掌，多次询问，求去掉 $1$ 到 $x$ 之间的简单路径，剩下的 $x$ 可以达到的节点中，颜色小于 $y$ 中，出现次数为奇数的颜色数或者出现次数为偶数次的颜色数。

我们先观察

去掉 $1$ 到 $x$ 之间的简单路径

实际上建出圆方树后，去掉 $1$ 到 $x$ 之间的简单路径，实际上就是把 $x$ 与上面全部断开，只留下以 $x$ 为根的子树。

剩下的问题很显然可以用线段树合并来写。

这时候实际上这道题已经做完了。

但是我们重新观察一下代码，发现建出圆方树然后在圆方树上面进行线段树合并来求子树和的过程和圆方树圆点方点加边的过程重复。

这时候我们就可以直接在 tarjan 算法运行的时候直接进行线段树合并。

上代码：

#include<cstdio>
#include<algorithm>
#include<vector>
#define N 1919810
#define M 3*N
using namespace std;
int n,m,o,l;
int head[N],to[N],nxt[N],tot;
int col[N],dfn[N],low[N],cnt,st[N],top;
int ans[N];
vector<pair<int,pair<int,int> > >q[N]; 
int rt[N];
void add(int u,int v){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
struct Segment_tree{
	int lson[M],rson[M];
	int js[M],os[M],cnt;
	#define lc lson[p]
	#define rc rson[p]
	#define mid (sl+sr)/2
	int pushup(int p){
		js[p]=os[p]=0;
		if(lc)js[p]+=js[lc],os[p]+=os[lc];
		if(rc)js[p]+=js[rc],os[p]+=os[rc];
		return p;
	}
	void insert(int &p,int sl,int sr,int x){
		if(!p)p=++cnt;
		if(sl==sr)return js[p]=1,void();
		if(mid>=x)insert(lc,sl,mid,x);
		else insert(rc,mid+1,sr,x);
		pushup(p);
	}
	int merge(int x,int y,int sl,int sr){
		if(!x||!y)return x+y;
		if(sl==sr){
			if(os[x]&&os[y])return x;
			if(js[x]&&os[y])return x;
			if(os[x]&&js[y])return y;
			js[x]=0,os[x]=1;
			return x;
		}
		lson[x]=merge(lson[x],lson[y],sl,mid);
		rson[x]=merge(rson[x],rson[y],mid+1,sr);
		return pushup(x);
	}
	int query(int p,int sl,int sr,int l,int r,int typ){
		if(!p)return 0;
		if(sl>r||sr<l)return 0;
		if(sl>=l&&sr<=r)return typ?js[p]:os[p];
		return query(lc,sl,mid,l,r,typ)+query(rc,mid+1,sr,l,r,typ);
	}
}t;
void tarjan(int x){
	st[++top]=x;
	dfn[x]=low[x]=++cnt;
	t.insert(rt[x],0,l,col[x]);
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]==dfn[x]){
				int z=0;
				do{
					z=st[top--];
					t.merge(rt[x],rt[z],0,l);
				}while(z!=y);
			}
		}else low[x]=min(low[x],dfn[y]);
	}
	for(int i=0;i<q[x].size();i++){
		int y=q[x][i].first;
		int typ=q[x][i].second.first;
		int id=q[x][i].second.second;
		ans[id]=t.query(rt[x],0,l,0,min(y,l),typ);	
	}
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&col[i]),l=max(l,col[i]);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	scanf("%d",&o);
	for(int i=1;i<=o;i++){
		int typ,x,y;
		scanf("%d%d%d",&typ,&x,&y);
		q[x].push_back(make_pair(y,make_pair(typ,i)));
	}
	tarjan(1);
	for(int i=1;i<=o;i++)printf("%d\n",ans[i]);
	return 0;
}