神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个到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;
}
发表回复