寒假学习计划
例题
给出一棵树,每个点上有一个数字.接着给出一系列形如x,y询问,对于每个询问,求x到y的路径上有多少个不同的数.
原理
欧拉序
如果想利用莫队解决这个树上的问题,一个很自然的想法是把这个树转化为一个序列,然后把询问操作区间化.传统的DFS序貌似并不合适,因为树上两点间的路径在DFS序中是不连续的.所以,在这里引入欧拉序的概念.
欧拉序一共有两种定义,这里针对以上问题先介绍一种.
和DFS序类似,欧拉序也是在DFS的过程中得到的.每次访问到一个点,就把它添加到欧拉序中,当这个点的所有儿子访问完毕后,再次把它添加到欧拉序中(故叶子节点会连续出现两次);并用st[x]和ed[x]表示节点x在欧拉序中最早和最晚出现的位置.
树上莫队
得到欧拉序后,下面针对询问操作进行处理.假设询问的两点是x和y,不妨设st[x]<st[y],即先访问x,后访问y.分两种情况讨论:
- $LCA(x,y)=x$,从欧拉序的定义不难推出,此时x和y位于同一条链上,这时被处理的区间是$[st[x],st[y]]$
- $LCA(x,y)!=x$.说明x和y不在同一条链上,这时被处理的区间是$[ed[x],st[y]]$
在被处理的区间中,一些点可能出现了两次,也可能只出现了一次.这时只需统计只出现了一次的点对答案的贡献即可.因为如果一个点出现了两次,说明它的所有子节点都已经被访问过了,最后又回到了自身.显然y一定不是这个点的子节点,而树上的路径是不会出现绕路的情况的,故这个点一定不会在x到y的路径上,所以不需要考虑.还有一点是,对于第二种情况,x和y的LCA是不会出现在区间中的(显然有 st[LCA]
问题转化完毕后,就可以开心地套莫队解决了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define N 40010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,x,y,tot,block,ans,L,lsum=1;
int col[N],head[N],st[N],ed[N],d[N],cnt[N],sum[N],p[20],f[N][20];
int w[N*2],pos[N*2],Ans[N*4];
map <int,int> M;
struct Edge{
int t,next;
}e[N*8];
struct Data{
int l,r,id,lca;
}a[N*4];
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline bool cmp(const Data a,const Data b){return (pos[a.l]==pos[b.l])?a.r<b.r:pos[a.l]<pos[b.l];}
inline int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
inline void Get_Euler(int x,int fa){
int i=0,s=0,j=0;
st[x]=++tot; w[tot]=x;
for (i=head[x];i;i=e[i].next)
if (e[i].t!=fa){
s=e[i].t; d[s]=d[x]+1;
f[s][0]=x;
for (j=1;j<=17;j++){
if (!f[s][j-1]) break;
f[s][j]=f[f[s][j-1]][j-1];
}
Get_Euler(s,x);
}
ed[x]=++tot; w[tot]=x;
}
inline int LCA(int x,int y){
int l=0,i=0;
if (d[x]<d[y]) Swap(x,y);
l=d[x]-d[y];
for (i=0;i<=17;i++)
if (l&p[i]) x=f[x][i];
if (x==y) return x;
for (i=17;i>=0;i--)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
inline void Update(int x){
sum[x]++;
if (sum[x]&1){
cnt[col[x]]++;
if (cnt[col[x]]==1) ans++;
} else {
cnt[col[x]]--;
if (!cnt[col[x]]) ans--;
}
}
inline void Solve(){
int l=1,r=0,i=0;
for (i=1;i<=m;i++){
while (r<a[i].r) Update(w[++r]);
while (r>a[i].r) Update(w[r--]);
while (l<a[i].l) Update(w[l++]);
while (l>a[i].l) Update(w[--l]);
if (a[i].lca) Update(a[i].lca);
Ans[a[i].id]=ans;
if (a[i].lca) Update(a[i].lca);
}
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
for (i=1;i<=n;i++){
col[i]=read();
if (!M[col[i]]) col[i]=M[col[i]]=++tot;
else col[i]=M[col[i]];
}
//for (i=1;i<=n;i++) cout<<col[i]<<endl;
tot=0;
for (i=1;i<n;i++){
x=read(); y=read();
Add(x,y); Add(y,x);
}
for (p[0]=i=1;i<=17;i++) p[i]=p[i-1]<<1;
Get_Euler(1,0);
// for (i=1;i<=n*2;i++) cout<<w[i]<<" "; cout<<endl;
block=int(sqrt(n*2));
for (i=1;i<=2*n;i++) pos[i]=(i-1)/block+1;
for (i=1;i<=m;i++){
x=read(); y=read();
if (st[x]>st[y]) Swap(x,y);
L=LCA(x,y);
a[i].id=i;
if (L==x) a[i].l=st[x],a[i].r=st[y];
else {
a[i].l=ed[x]; a[i].r=st[y];
a[i].lca=L;
}
// cout<<a[i].l<<" "<<a[i].r<<" "<<a[i].lca<<endl;
}
sort(a+1,a+1+m,cmp);
Solve();
for (i=1;i<=m;i++) printf("%d\n",Ans[i]);
return 0;
}
注:以上代码其实还有一定的优化空间,倍增LCA可以替换成树剖LCA,莫队也可以再套一个奇偶优化.
欧拉序的应用
上面提到欧拉序一共有两种,第一种可以用于树上莫队.
还有一个比较重要的应用是求子树权值和.
例如给出一棵树和每个点的点权.一种操作是把某个子树的所有点的权值加上一个数.每一个询问是求某个子树的权值和.这不是DFS序裸题吗,线段树区间修改区间求和
使用第一种欧拉序的话,不难观察到一个节点第一次和最后一次出现的位置之间的所有点恰好是其子树中的所有节点,所以可以打差分去解决这个问题.
第二种欧拉序是,每当DFS访问到一个节点就把它添加到序列中.
这种欧拉序可以在O(1)的时间内求LCA.不妨设 st[x]
