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

约定不等于承诺〃 2021-11-02 10:20 283阅读 0赞

#### 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 ####

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

#### Data Constraint ####

![Image 1][]

# 题解 #

*  首先先将树分块，然后把区间排序，按照第一权值为左端点所在块的编号，右端点在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 }

转载于:https://www.cnblogs.com/Comfortable/p/11176136.html

[Image 1]: