【BZOJ3757】苹果树

  树上莫队的模板题。前置技能BZOJ1086的树分块，然后和序列上的莫队差不多的做法。询问按第一关键字为左端点所在块，第二关键字为右端点的DFS序排序。

  维护当前路径上有哪些点的时候不记录两端点的公共祖先，这样操作比较好。

  另外对每个从u到v的询问，如果u所在块大于v所在块就交换u和v。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=50010,maxm=100010;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

struct Query {int u,v,a,b,block,id;}Q[maxm];

int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
int Col[maxn];
int n,m,V;

void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}

int DFSID[maxn],IDs;
int belong[maxn],Bcnt;
int fa[maxn][20],dep[maxn];
int stack[maxn],top;
void DFS(int x,int father,int depth)
{
	int bottom=top;
	dep[x]=depth;
	fa[x][0]=father;
	for (int l=0;fa[fa[x][l]][l];l++) fa[x][l+1]=fa[fa[x][l]][l];
	DFSID[x]=++IDs;
	for (int i=head[x];i;i=next[i]) if (E[i]!=father)
	{
		DFS(E[i],x,depth+1);
		if (top-bottom>=V)
		{
			++Bcnt;
			while (top>bottom) belong[stack[top--]]=Bcnt;
		}
	}
	stack[++top]=x;
}

void Init()
{
	read(n),read(m);
	while (V*V<n) V++;
	for (int i=1;i<=n;i++) read(Col[i]);
	for (int i=1,x,y;i<=n;i++)
	{
		read(x),read(y);
		if (x&&y) Add_Edge(x,y);
	}
	DFS(1,0,1);
	Bcnt++;
	while (top) belong[stack[top--]]=Bcnt;
}

bool cmp(const Query &a,const Query &b) {return a.block<b.block || a.block==b.block && DFSID[a.v]<DFSID[b.v];}
int vis[maxn],colcnt[maxn],ans[maxm],res;

int LCA(int u,int v)
{
	if (dep[u]<dep[v]) swap(u,v);
	int l=0,dis=dep[u]-dep[v];
	while (dis)
	{
		if (dis&1) u=fa[u][l];
		dis>>=1;
		l++;
	}
	l=0;
	while (fa[u][l]!=fa[v][l]) l++;
	while (l>=0)
	{
		if (fa[u][l]!=fa[v][l]) u=fa[u][l],v=fa[v][l];
		l--;
	}
	if (u!=v) u=fa[u][0],v=fa[v][0];
	return u;
}

void Update(int u,int v)
{
	v=fa[v][0];
	while (u!=v)
	{
		if (!vis[u])
		{
			colcnt[Col[u]]++;
			if (colcnt[Col[u]]==1) res++;
			vis[u]=1;
		}
		else
		{
			colcnt[Col[u]]--;
			if (colcnt[Col[u]]==0) res--;
			vis[u]=0;
		}
		u=fa[u][0];
	}
}

void Solve()
{
	for (int i=1;i<=m;i++)
	{
		read(Q[i].u),read(Q[i].v),read(Q[i].a),read(Q[i].b),Q[i].id=i;
		if (belong[Q[i].u]>belong[Q[i].v]) swap(Q[i].u,Q[i].v);
		Q[i].block=belong[Q[i].u];
	}
	sort(Q+1,Q+1+m,cmp);
	int u=1,v=1;
	for (int i=1;i<=m;i++)
	{
		int lca=LCA(u,Q[i].u);
		Update(u,lca);
		Update(Q[i].u,lca);
		lca=LCA(v,Q[i].v);
		Update(v,lca);
		Update(Q[i].v,lca);
		u=Q[i].u;v=Q[i].v;
		lca=LCA(u,v);
		Update(lca,lca);
		if (Q[i].a==Q[i].b) ans[Q[i].id]=res;
		else if (colcnt[Q[i].a] && colcnt[Q[i].b]) ans[Q[i].id]=res-1;else ans[Q[i].id]=res;
		Update(lca,lca);
	}
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
}

int main()
{
	Init();
	Solve();
	return 0;
}