【BZOJ 3575】苹果树

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3757
数据传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/3757.rar

树上莫队的模板题!
真的是好板,只要会树分块就可以写辣!

然而树上莫队有几个地方必须要注意:
1.排序的时候必须以一个点的所在树块的编号为第一关键字,然后第二关键字搞成另一点的DFS序
2.最好把每个询问的两个点中DFS较大的作为第二个点
以上这么做为什么会极大的影响速度并不是太清楚 ╮(╯▽╰)╭ 不过效果真的很好
还有不会的同学,出门左拐去找PoPoQQQ吧:http://blog.csdn.net/popoqqq/article/details/41479829

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 50000+9;
const int M = 100000+9;

int head[N],to[M],nxt[M],n,m,col[N],stk[M],top,LIM,dfs_num[M];
int fa[N][17],dep[N],cnt[N],ans,num[N],vout[M],sta[N]; 
struct Query{
	int u,v,a,b,id;
	bool operator < (const Query &B) const {
		return num[u] < num[B.u] || (num[u] == num[B.u] && dfs_num[v] < dfs_num[B.v]);
	}
}query[M];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

void DFS(int w, int f, int bot) {
	static int block_cnt = 0;
	static int dfs_cnt = 0;
	
	dfs_num[w] = ++dfs_cnt;
	fa[w][0] = f; dep[w] = dep[f] + 1; 
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS(to[i],w,top);
			if (top - bot >= LIM) {
				block_cnt++;
				while (top > bot) {
					num[stk[top--]] = block_cnt;				
				}
			}
		}
	}
	stk[++top] = w;
	while (!w && top) {
		num[stk[top--]] = block_cnt;
	}
}

inline void update(int id, bool delta) {
	if (cnt[id] == 1 && !delta) ans--;
	else if (!cnt[id] && delta) ans++;
	cnt[id] += delta?1:-1;
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x,y);
	for (int i=16;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y) return x;
	for (int i=16;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

inline void move(int &w, int pur) {
	int lca = LCA(w, pur);
	for (int i=w;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1);
	for (int i=pur;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1);
	w = pur;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

int main(){
	int size = 128 << 20; 
	char *p = (char*)malloc(size) + size;  
	__asm__("movl %0, %%esp\n" :: "r"(p)); 
	
	n = read(); m = read(); LIM = sqrt(n) + 1;
	for (int i=1;i<=n;i++) col[i] = read();
	for (int i=1;i<=n;i++) Add_Edge(read(), read());
	DFS(0,0,0);
	for (int i=1;i<=16;i++) {
		for (int j=0;j<=n;j++) {
			fa[j][i] = fa[fa[j][i-1]][i-1];
		}
	}
	for (int i=1;i<=m;i++) {
		query[i].id = i;
		query[i].u = read(); 
		query[i].v = read();
		query[i].a = read();
		query[i].b = read();
		if (dfs_num[query[i].u] > dfs_num[query[i].v]) {
			swap(query[i].u, query[i].v);
		}
	}
	sort(query+1, query+1+m);
	
	for (int i=1,p1=0,p2=0;i<=m;i++) {
		move(p1, query[i].u);
		move(p2, query[i].v);
		
		int lca = LCA(query[i].v, query[i].u);
		update(col[lca], sta[lca] ^= 1);
		vout[query[i].id] = ans;
		if (query[i].a != query[i].b && cnt[query[i].a] && cnt[query[i].b]) vout[query[i].id]--;
		update(col[lca], sta[lca] ^= 1);
	}
	
	for (int i=1;i<=m;i++) {
		printf("%d\n",vout[i]);
	}
	return 0;
}