SPOJ COT2 （树上莫队）

传送门

题意：

给你一棵大小为$n$的树，每个点都有点权。现在有$m$个询问，每个询问给你一个两个数$a,b$，问你从点$a$到点$b$之间的路径中不同的点权的个数。

分析：

万恶的spoj并没有写点权的数据范围，害我我先re（此题需要离散化点权）

求解带有询问的不同数的个数这类题，一看就相当莫队 ，但是因为莫队只能够在一个序列上进行操作，因此我们考虑如何让树的树形结构转化为线性的结构。

我们考虑使用树的欧拉序。

我们设$st[]$为第一次遍历经过的编号，$en[]$为回溯时经过的编号，则现在有两种方案：

如果两个节点$a,b$在同一条链上，则我们直接选取欧拉序区间$([st[a],st[b])$如果两个结点不在同一条链上，则我们直接选取欧拉序区间$(en[a],st[b])$

对于每个区间，我们只需要统计该区间中，数字只出现一次的数字的个数。

与此同时，因为在操作$2$中，两个节点的最近公共祖先是没有被贡献的，因此我们还得加上$LCA(a,b)$的贡献。

之后就是我们普通莫队的分块了。

#include <bits/stdc++.h> #define maxn 200005 #define K 20 using namespace std; struct P{ int l,r,z,id; }Q[maxn]; struct Node{ int to,next; }q[maxn<<1]; int lim,Cnt,pos[maxn<<1],c[maxn]; int n,m,loc[maxn<<1],dfn,st[maxn],en[maxn],d[maxn],f[maxn][25]; int ans[maxn],cnt[maxn],sum,head[maxn]; bool vis[maxn]; bool cmp(const P&a,const P&b){ return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l]; } void add_edge(int from,int to){ q[Cnt].to=to; q[Cnt].next=head[from]; head[from]=Cnt++; } void dfs(int x){ loc[st[x]=++dfn]=x; vis[x]=1; for(int i=1;i<=K;i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=head[x];i!=-1;i=q[i].next){ int to=q[i].to; if(!vis[to]) d[to]=d[f[to][0]=x]+1,dfs(to); } loc[en[x]=++dfn]=x; } int lca(int x,int y){ if(x==y)return x; if(d[x]<d[y])swap(x,y); for(int i=K;~i;i--) if(d[f[x][i]]>=d[y])x=f[x][i]; if(x==y) return x; for(int i=K;~i;i--){ if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; } return f[x][0]; } void deal(int x){ if(!vis[x]){ if(!(--cnt[c[x]])) sum--; } else if(!(cnt[c[x]]++)) sum++; vis[x]^=1; } int D[maxn]; int main() { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); Cnt=0; for(int i=1;i<=n;i++){ scanf("%d",&c[i]); D[i]=c[i]; } sort(D+1,D+1+n); for(int i=1;i<=n;i++) c[i]=lower_bound(D+1,D+1+n,c[i])-D; for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); add_edge(x,y),add_edge(y,x); } dfs(d[1]=1),lim=(int)sqrt(n*2+0.5); for(int i=1;i<=dfn;i++) pos[i]=(i-1)/lim+1; for(int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); Q[i].id=i; if(st[x]>st[y]) swap(x,y); int z=lca(x,y); if(z==x) Q[i].l=st[x],Q[i].r=st[y]; else Q[i].l=en[x],Q[i].r=st[y],Q[i].z=z; } sort(Q+1,Q+1+m,cmp); int l=1,r=0; for(int i=1;i<=m;i++){ while(r<Q[i].r) deal(loc[++r]); while(r>Q[i].r) deal(loc[r--]); while(l<Q[i].l) deal(loc[l++]); while(l>Q[i].l) deal(loc[--l]); if(Q[i].z) deal(Q[i].z); ans[Q[i].id]=sum; if(Q[i].z) deal(Q[i].z); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); }