记录编号	357341	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]地图	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.052 s
提交时间	2016-12-10 19:35:38	内存使用	89.19 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=500010;
//=============边表============
struct edge{int f,t,o;bool vis;}w[N];
int n,m,head[N],tail[N],next[N];
inline void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
//=============建树============
int fa[N],Fa[N],v[N];
void dfs(int x){//仙人掌化树 
	for (int i=head[x];i;i=next[i])
	if (!w[i].vis){
		w[i].vis=w[w[i].o].vis=1;
		int u=w[i].t;
		if (!fa[u]) fa[u]=Fa[u]=x,dfs(u);
		else for (int v=x;v!=w[i].t;v=Fa[v]) fa[v]=u;
	}
}
int s[N],dfn[N],cnt,q[N],pos[N],size;
vector<int> e[100010];
void dfs1(int x){//求size 
	dfn[x]=++cnt;
	q[++size]=x;
	pos[x]=size;
	s[x]=1;
	for (int i=e[x].size()-1;i>=0;i--){
		q[++size]=x;
		int v=e[x][i];
		dfs1(v);
		s[x]+=s[v];
	}
}
//=============LCA============
int dp[N][20],t[20],lg[N];
void init_st(){//ST求LCA 
	for (int i=1;i<=size;i++) dp[i][0]=q[i];
	t[0]=1;
	for (int i=1;i<19;i++){
		t[i]=1<<i;
		for (int j=t[i-1];j<t[i];j++) lg[j]=i-1;
	}
	for (int j=1;j<19;j++)
	for (int i=1;i<=size-t[j]+1;i++){
		int lc=dp[i][j-1],rc=dp[i+t[j-1]][j-1];
		dp[i][j]=(dfn[lc]<dfn[rc]?lc:rc);
	}
}
int lca(int x,int y){
	x=pos[x];y=pos[y];
	if (x>y) swap(x,y);
	int k=lg[y-x+1],lc=dp[x][k],rc=dp[y-t[k]+1][k];
	return dfn[lc]<dfn[rc]?lc:rc;
}
//=============子树求和============
struct bit{
	int a[N];
	void add(int p,int d){
		if (!p) return;
		for (;p<=n;p+=(p&-p)) a[p]+=d;
	}
	int sum(int r){
		int ans=0;
		for (;r;r-=(r&-r)) ans+=a[r];
		return ans;
	}
	int treesum(int x){
		return sum(dfn[x]+s[x]-1)-sum(dfn[x]-1);
	}
}odd,even;
//=============求解============
struct opt{//k=1表示加点,k=2表示询问,x为操作点,y为参数,id为询问时刻 
	int k,ty,x,y,id;
}Q[N];
bool cmp(const opt &x,const opt &y){
	return x.y==y.y?x.k<y.k:x.y<y.y;
}
struct sit{
	int p,k;
	sit(int P=0){p=P;k=dfn[p];}
	bool operator < (const sit &x)const{return k<x.k;}
};
priority_queue<sit> H;
int X[N],sum[N],color[N],ans[N];//当前各个节点该种拉面出现次数 
void visit(int x,int C){
	if (color[x]==C) return;
	color[x]=C;
	Fa[x]=sum[x]=0;
	H.push(x);
}
void solve(int l,int r){
	static int C=0;C++;
	for (int i=l;i<=r;i++)
		visit(X[i],C),sum[X[i]]++;
	while (!H.empty()){
		int v=H.top().p;H.pop();
		if (!H.empty()){
			int u=H.top().p;
			Fa[v]=lca(u,v);
			visit(Fa[v],C);
			sum[Fa[v]]+=sum[v];
		}
		bit *T=(sum[v]&1?&odd:&even);
		T->add(dfn[v],1);
		T->add(dfn[Fa[v]],-1);
	}
}
int main()
{
	freopen("map_2016.in","r",stdin);
	freopen("map_2016.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&v[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&w[i].f,&w[i].t);
		w[i+m]=w[i];
		swap(w[i].f,w[i].t);
		w[i].o=i+m;
		w[i+m].o=i;
		add(w[i].f,i);
		add(w[i].t,i+m);
	}
	Fa[1]=fa[1]=1;dfs(1);
	for (int i=2;i<=n;i++) e[fa[i]].push_back(i);
	dfs1(1);init_st();
	int q;scanf("%d",&q);
	for (int i=1;i<=q;i++){
		scanf("%d%d%d",&Q[i].ty,&Q[i].x,&Q[i].y);
		Q[i].id=i;Q[i].k=2;
	}
	for (int i=1;i<=n;i++)
		Q[q+i].k=1,Q[q+i].x=i,Q[q+i].y=v[i];
	sort(Q+1,Q+q+n+1,cmp);
	for (int i=1;i<=q+n;){
		int flag=Q[i].y,l=i;
		for (;i<=q+n&&Q[i].y==flag&&Q[i].k==1;X[i]=Q[i].x,i++);
		solve(l,i-1);
		for (;i<=q+n&&Q[i].y==flag&&Q[i].k==2;i++)
		if (Q[i].ty==1)
			ans[Q[i].id]=odd.treesum(Q[i].x);
		else
			ans[Q[i].id]=even.treesum(Q[i].x);
	}
	for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}