莫队算法，先处理dfs序，然后将询问进行一下处理，假设询问x,y两点，x的的dfs序区间是[xl,xr],y的dfs序是[yl,yr]，那么这两个区间如果包含，那么询问区间[min(xl,yl),max(xl,yl)]，否则询问区间[min(xr,yr),max(xl,yl)]。对于算法当前处理的一个区间的删除插入操作，假设要判断一个点x是否出现在当前区间维护的路径中，如果其dfs区间被当前区间包含或者其记录的出现次数为0，说明该点其实是不存在的，否则存在。
代码
1 #include<cstdio> 2 #include<algorithm> 3 #define N 2000010 4 using namespace std; 5 int dp,p[N],pre[N],tt[N],l[N],r[N],tot,o[N]; 6 int L,R,ans[N],sum[N],cnt,flag1[N],flag2[N],flag3[N],colsum[N]; 7 int n,m,i,col[N],a,b; 8 struct g{ 9 int l,r,ca,cb,id; 10 }q[N]; 11 void link(int x,int y) 12 { 13 dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y; 14 } 15 void dfs(int x,int fa) 16 { 17 int i=p[x]; 18 l[x]=++tot; 19 o[tot]=x; 20 while (i) 21 { 22 if (tt[i]!=fa) 23 { 24 dfs(tt[i],x); 25 o[++tot]=x; 26 } 27 i=pre[i]; 28 } 29 if (tot==l[x]) o[++tot]=x; 30 r[x]=tot; 31 } 32 void cc(int x,int w) 33 { 34 int t=o[x]; 35 if (t==0) return; 36 sum[t]+=w; 37 if (x==l[t]) if (w==-1) flag1[t]=0;else flag1[t]=1; 38 if (x==r[t]) if (w==-1) flag2[t]=0;else flag2[t]=1; 39 if ((sum[t])&&((flag1[t]&&flag2[t])==0)) 40 { 41 if (!flag3[t]) 42 { 43 if (colsum[col[t]]==0) cnt++; 44 colsum[col[t]]++; 45 } 46 flag3[t]=1; 47 } 48 else 49 { 50 if (flag3[t]) 51 { 52 if (colsum[col[t]]==1) cnt--; 53 colsum[col[t]]--; 54 } 55 flag3[t]=0; 56 } 57 } 58 bool cmp(g a,g b) 59 { 60 if (a.l/500==b.l/500) 61 return a.r<b.r; 62 return a.l/500<b.l/500; 63 } 64 int main() 65 { 66 scanf("%d%d",&n,&m); 67 for (i=1;i<=n;i++) 68 scanf("%d",&col[i]); 69 for (i=1;i<=n;i++) 70 { 71 scanf("%d%d",&a,&b); 72 link(a,b);link(b,a); 73 } 74 dfs(0,-1); 75 for (i=1;i<=m;i++) 76 { 77 scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].ca,&q[i].cb);q[i].id=i; 78 int ta=q[i].l;int tb=q[i].r; 79 if (r[ta]<l[tb]) q[i].l=r[ta],q[i].r=l[tb]; 80 else 81 if (r[tb]<l[ta]) q[i].l=r[tb],q[i].r=l[ta]; 82 else 83 if (l[ta]<l[tb]) q[i].l=l[ta],q[i].r=l[tb]; 84 else q[i].l=l[tb],q[i].r=l[ta]; 85 } 86 87 sort(q+1,q+1+m,cmp); 88 L=1;R=0; 89 for (i=1;i<=m;i++) 90 { 91 while (R<q[i].r)R++,cc(R,1); 92 while (R>q[i].r)cc(R,-1),R--; 93 while (L<q[i].l)cc(L,-1),L++; 94 while (L>q[i].l)L--,cc(L,1); 95 ans[q[i].id]=cnt; 96 if (colsum[q[i].ca]&&colsum[q[i].cb]&&(q[i].ca!=q[i].cb)) ans[q[i].id]--; 97 } 98 for (i=1;i<=m;i++) 99 printf("%d ",ans[i]); 100 }