「BZOJ3757」苹果树

神犇家门口种了一棵苹果树。苹果树作为一棵树,当然是呈树状结构,每根树枝连接两个苹果,每个苹果都可以沿着一条由树枝构成的路径连到树根,而且这样的路径只存在一条。由于这棵苹果树是神犇种的,所以苹果都发生了变异,变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码,号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。

有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题,才能进屋膜拜神犇。这个问题就是,从树上编号为u的苹果出发,由树枝走到编号为v的苹果,路径上经过的苹果一共有多少种不同的颜色(包括苹果u和苹果v的颜色)?不过神犇注意到,有些来膜拜的人患有色盲症。具体地说,一个人可能会认为颜色a就是颜色b,那么他们在数苹果的颜色时,如果既出现了颜色a的苹果,又出现了颜色b的苹果,这个人只会算入颜色b,而不会把颜色a算进来。

神犇是一个好人,他不会强人所难,也就会接受由于色盲症导致的答案错误(当然答案在色盲环境下也必须是正确的)。不过这样神犇也就要更改他原先数颜色的程序了。虽然这对于神犇来说是小菜一碟,但是他想考验一下你。你能替神犇完成这项任务吗?

Input

输入第一行为两个整数n和m,分别代表树上苹果的个数和前来膜拜的人数。

接下来的一行包含n个数,第i个数代表编号为i的苹果的颜色Coli。

接下来有n行,每行包含两个数x和y,代表有一根树枝连接了苹果x和y(或者根和一个苹果)。

接下来有m行,每行包含四个整数u、v、a和b,代表这个人要数苹果u到苹果v的颜色种数,同时这个人认为颜色a就是颜色b。如果a=b=0,则代表这个人没有患色盲症。

Output

输出一共m行,每行仅包含一个整数,代表这个人应该数出的颜色种数。

Sample Input

5 3

1 1 3 3 2

0 1

1 2

1 3

2 4

3 5

1 4 0 0

1 4 1 3

1 4 1 2

Sample Output

2

1

2

HINT

0<=x,y,a,b<=N

N<=50000

1<=U,V,Coli<=N

树上莫队,可参照这篇不错的博客

#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();int f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}
	x*=f;
}

const int N = 100050;
int n,m,va[N],u,v,tim = 0,dfn[N],depth[N],fff[N][16],buc[N] = {0},taken[N] = {0},ans = 0,blc,rans[N];
vector<int> G[N];
void dfs(int num,int fa = -1){
	tim++;
	dfn[num] = tim;
	fff[num][0] = fa;
	for(int i=1;i<=15;i++)fff[num][i] = fff[fff[num][i-1]][i-1];
	for(int i=0;i<G[num].size();i++){
		int ct = G[num][i];
		if(ct == fa)continue;
		depth[ct] = depth[num]+1;
		dfs(ct,num);
	}
}
int lca(int u,int v){
	if(depth[u]<depth[v])swap(u,v);
	for(int i=15;i>=0;i--)if(fff[u][i]!=-1 && depth[fff[u][i]] >=depth[v])u = fff[u][i];
	for(int i=15;i>=0;i--)if(fff[u][i]!=-1&&fff[v][i]!=-1&&fff[u][i]!=fff[v][i])u=fff[u][i],v=fff[v][i];
	if(u == v)return u;
	return fff[u][0];
}
struct query{
	int l,r,a,b,id;
	bool operator < (const query &rhs) const{
		if(dfn[l]/blc!=dfn[rhs.l]/blc)
			return dfn[l]/blc<dfn[rhs.l]/blc;
		return dfn[r]<dfn[rhs.r];
	}
}Q[N];

inline void chg(int x){
	if(taken[x]){
		if(buc[va[x]] == 1)ans--;
		buc[va[x]]--;
		taken[x] = 0;
	}else{
		if(buc[va[x]] == 0)ans++;
		buc[va[x]]++;
		taken[x] = 1;
	}
}
void mov(int u,int v){
	if(depth[u]<depth[v])swap(u,v);
	while(depth[u]>depth[v]){
		chg(u);
		u = fff[u][0];
	}
	while(u!=v){
		chg(u);chg(v);
		u = fff[u][0];
		v = fff[v][0];
	}
}
int main() {
	read(n);read(m);
	blc = sqrt(n)+1;
	for(int i=1;i<=n;i++)read(va[i]);
	for(int i=1;i<=n;i++){
		read(u);read(v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	depth[0] = 0;
	dfs(0);
	for(int i=0;i<m;i++){
		read(Q[i].l);read(Q[i].r);read(Q[i].a);read(Q[i].b);Q[i].id = i;
		if(dfn[Q[i].l]>dfn[Q[i].r])swap(Q[i].l,Q[i].r);
	}
	sort(Q,Q+m);
	int ccl = 0,ccr = 0;
	for(int i=0;i<m;i++){
		int cl = Q[i].l,cr = Q[i].r;
		mov(ccl,cl);
		mov(ccr,cr);
		ccl = cl;ccr = cr;
		cl = lca(ccl,ccr);
		chg(cl);
		rans[Q[i].id] = ans-(Q[i].a!=Q[i].b&&buc[Q[i].a] && buc[Q[i].b]);
		chg(cl);
	}
	for(int i=0;i<m;i++)cout<<rans[i]<<'\n';
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注