[树上莫队][lca] Jzoj P3360 苹果树

2022-08-20 13:13:45

Description

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

有许许多多的人来神犇家里膜拜神犇。可神犇可不是随便就能膜拜的。前来膜拜神犇的人需要正确回答一个问题，才能进屋膜拜神犇。这个问题就是，从树上编号为N的苹果出发，由树枝走到编号为N的苹果，路径上经过的苹果一共有多少种不同的颜色（包括苹果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

Sample Output

Data Constraint

题解

首先先将树分块，然后把区间排序，按照第一权值为左端点所在块的编号，右端点在DFS序中的位置排序，关键是转移
对于任意一个状态，在树上表示[l,r]的路径，目前的状态只存{x|x∈[l,r],x != LCA(l,r)}这些点的颜色
这样就大概有两种情况，一种是两条链，没有中间的LCA，或者是一条链，没有顶端的LCA
然后一直这样转移，例如从[l,r]转移到[x,y]的时候，我们只需要暴力从l->x,y->r，注意记录一个标记数组，在转移的时候把路径上的所有点取反
这样转移之后还是{x|x∈[l,r],x != LCA(l,r)}这些点
统计答案的时候将LCA加回来，然后再删掉

代码

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define N 50010
 7 #define M 100010
 8 using namespace std;
 9 struct node { int l,r,x,y,s,t,id,p; }Q[M];
10 struct edge { int to,from; }e[N*2];
11 int n,m,cnt,tot,top,l,r,col[N],head[N],p[N],q[N],deep[N],num[N],ans[M],bel[N*2],a[N*2],f[N][20];
12 bool bz[N];
13 bool cmp(node a,node b) { return bel[a.l]<bel[b.l]||bel[a.l]==bel[b.l]&&a.r<b.r; }
14 void insert(int x,int y)
15 {
16     e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt;
17     e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt;
18 }
19 void dfs(int x,int fa)
20 {
21     deep[x]=deep[fa]+1,f[x][0]=fa,a[++top]=x,p[x]=top;
22     for (int i=head[x];i;i=e[i].from) if (e[i].to!=fa) dfs(e[i].to,x);
23     a[++top]=x,q[x]=top; 
24 }
25 void change(int x)
26 {
27     if (bz[x])
28     {
29         num[col[x]]--;
30         if (num[col[x]]==0) tot--;
31     }
32     else 
33     {
34         num[col[x]]++;
35         if (num[col[x]]==1) tot++;
36     }
37     bz[x]^=1;
38 }
39 int LCA(int x,int y)
40 {
41     if (deep[x]<deep[y]) swap(x,y);
42     for (int i=16;i>=0;i--) if (deep[f[x][i]]>=deep[y]) x=f[x][i];
43     if (x==y) return x;
44     for (int i=16;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
45     return f[x][0];
46 }
47 int main()
48 {
49     scanf("%d%d",&n,&m);
50     for (int i=1;i<=n;i++) scanf("%d",&col[i]);
51     for (int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); if (x&&y) insert(x,y); }
52     dfs(1,0);
53     for (int j=1;j<=16;j++) for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
54     for (int i=1,x,y;i<=m;i++)
55     {
56         scanf("%d%d",&x,&y),Q[i].x=x,Q[i].y=y;
57         if (p[x]>p[y]) swap(x,y);
58         if (p[y]<q[x]) Q[i].l=p[x],Q[i].r=p[y],Q[i].p=0; else Q[i].l=q[x],Q[i].r=p[y],Q[i].p=1;
59         scanf("%d%d",&Q[i].s,&Q[i].t),Q[i].id=i;
60     }
61     int K=floor(sqrt(n*2))+1;
62     for (int i=1;i<=n*2;i++) bel[i]=(i-1)/K+1;
63     sort(Q,Q+m+1,cmp),l=r=1,change(a[1]);
64     for (int i=1,x,y,lca;i<=m;i++)
65     {
66         while (l<Q[i].l) change(a[l++]);
67         while (l>Q[i].l) change(a[--l]);
68         while (r<Q[i].r) change(a[++r]);
69         while (r>Q[i].r) change(a[r--]);
70         if (Q[i].p) x=Q[i].x,y=Q[i].y,lca=LCA(x,y),change(lca);
71         int j=tot; x=Q[i].s,y=Q[i].t;
72         if (x!=y&&num[x]&&num[y]) j--;
73         ans[Q[i].id]=j;
74         if (Q[i].p) change(lca); 
75     } 
76     for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
77 }