基础莫队算法和带修莫队操作的基础都是一维数组。其他问题如果能转换为一维数组上的区间问题，那么也能应用莫队算法。

典型的类型就是树形结构上的路径问题，可以利用“欧拉序” 把整颗树的节点顺序转换为一个一维数组，路径问题也变成了区间问题，就能利用莫队算法求解。

例1. SP10707 COT2 - Count on a tree II

【题意简化】给定 $n$ 个结点的树，每个结点有一种颜色。 $m$ 次询问，每次询问给出 $u,v$，回答 $u,v$ 之间的路径上的结点的不同颜色数。颜色编号是不超过 $2×10^9$ 的非负整数，数据范围：$1≤n≤4×10^4，1≤m≤10^5$

【分析】 树上莫队，利用欧拉序，将树上路径问题改变为区间上的问题。

首先把树的节点用欧拉序转换为一维数组。

欧拉序是 DFS 遍历中记录每个节点 进入、 回溯、离开 节点均记录，完整记录树的遍历轨迹。回溯时可以不记录节点，一般欧拉序有两种遍历方式：

• DFS 时记录每个节点“进入、离开” ：每个节点第一次访问和最后离开时，加入序列，每个节点加两遍。子树会构成区间形式，也称为括号序。如下图，欧拉序为：[1,2,5,5,2,3,6,6,7,7,8,8,3,4,4,1]

• DFS 时记录每个节点进入、回溯：每个节点访问和回溯回来的时候，都加入序列。这种方式可以求 lca ,两个节点间深度最小值就是 lca。如下图，另外一种欧拉序为：[1,2,5,2,1,3,6,3,7,3,8,3,1,4,1]

欧拉序例子

对于树上莫队，使用第一种欧拉序（括号序）。

对于路径以外的子树节点对应区间都会出现两次，如果第一次加入，第二次删除，相当于对答案没有影响。但考虑到 lca ,分两种情况讨论：

（1） $LCA(u,v)= u$ 或 $LCA(u,v)= u$, 查询 u,v 之一是 lca: 例如路径 1,8, 以进入位置为下标，对应的区间就是 [1,2,5,5,2,3,6,6,7,7,8] ,只出现一次，就是这条路径，即 [1,3,8]。

莫队对应区间是 $[first_u,first_v]$ ,其中 $first_u、first_v$ 是查询节点 $u$ 和 $v$ 在欧拉序开始位置。

（2）$LCA(u,v)\ne u, LCA(u,v)\ne v$ ，查询 u,v 都不是 lca 。此时 u 和 v 之间的路径需要通过它们的 LCA ,但是 LCA 没有出现在 u 和 v 的欧拉序区间内，需要添加上。例如，u=6,v=4 ,对应的区间是 [6,7,7,8,8,3,4] ,去掉两次出现，就是 [6,3,4]，再加上 lca=1, 就可以得到路径 [6,3,1,4]。

莫队对应区间是 $[last_u,first_v]$ ,其中 $last_u$ 是查询节点 $u$ 欧拉序结束位置，$first_v$ 是 $v$ 在欧拉序开始位置。

注意这种情况，对于每种情况，加上 lca 的贡献，之后需要删除 lca 的贡献。

【参考代码】

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+10,M=1e5+10;
int head[N],tot;
struct node{
	int to,next;
}edge[N<<1]; 
struct nodeq
{
	int l,r,lca;
	int id;
}q[M];
int dep[N],ola[N<<1],fa[N][30],first[N],last[N],cnt;
//ola[] 欧拉序 
//first[i] last[i] 节点i在欧拉序开始\结束位置 cnt 欧拉序计数编号 
int len,ans,qans[M],col[N];
//len为分块的大小
//ans统计颜色数 qans[i] 第i次询问的答案 
int n,m,a[N],b[N];
//a[i]节点i的颜色编号 b数组用于离散化 
void add(int from,int to)
{
	edge[++tot].to=to;
	edge[tot].next=head[from];
	head[from]=tot;
} 
void dfs(int x,int father)
 {
 	ola[++cnt]=x; 
 	first[x]=cnt;
	for(int i=head[x];i;i=edge[i].next)
	{
		int y=edge[i].to;
		if(y==father)continue;
		dep[y]=dep[x]+1;
		fa[y][0]=x;
		for(int i=1;(1<<i)<=dep[y];++i)
			fa[y][i]=fa[fa[y][i-1]][i-1];
		dfs(y,x);
	}  
	ola[++cnt]=x;
	last[x]=cnt;
}
int getlca(int u,int v)
{
	if(dep[u]>dep[v])swap(u,v);
	for(int i=20;i>=0;i--)
		if(dep[fa[v][i]]>=dep[u])v=fa[v][i];
	if(u==v)return u;
	for(int i=20;i>=0;i--)
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void add(int x)
{
	if(col[x]==0)ans++;
	col[x]++;
	
}
void del(int x)
{
	if(col[x]==1)ans--;
	col[x]--;
	
}
bool vis[N];   //vis[i]表示位置i是否在统计区间内 1 表示在统计区间内 0 表示不在统计区间内 
void work(int pos) {
	if(vis[pos])del(a[pos]);
	else add(a[pos]);
	vis[pos]^=1;
}

int cmp(nodeq a,nodeq b)
{
	return (a.l/len ==b.l/len)?(a.r<b.r):(a.l<b.l);
 } 

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",a+i),b[i]=a[i];
	
	//离散化
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+n+1,a[i])-b;   
		 
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u); 
	} 
	dep[1]=1;
	dfs(1,-1);
		
	for(int i=1;i<=m;i++)
	{
		int x,y,lca;
		scanf("%d%d",&x,&y);
		lca=getlca(x,y);
		if(first[x]>first[y])swap(x,y);
		if(x==lca){
			q[i].l=first[x];
			q[i].r=first[y];
		}
		else
		{
			q[i].l=last[x];
			q[i].r=first[y];
			q[i].lca=lca;
		}
		q[i].id=i;
	}
	len=sqrt(n); //块的大小 
	sort(q+1,q+m+1,cmp);
	
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		int ql=q[i].l,qr=q[i].r,lca=q[i].lca;
		while(l>ql)work(ola[--l]);
		while(r<qr)work(ola[++r]);
		while(l<ql)work(ola[l++]);		
		while(r>qr)work(ola[r--]);
						
		if(lca)add(a[lca]);
		qans[q[i].id]=ans;
		if(lca)del(a[lca]);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",qans[i]);
	return 0;
}

例2. P4074 [WC2013] 糖果公园

【题意简化】给定 $n$ 个节点的树，树上第 $𝑖$ 个点颜色为 $𝑐_𝑖$，每次询问一条路径 $𝑢_𝑖,𝑣_𝑖$, 求这条路径上的

$\sum_𝑐{𝑣𝑎𝑙_𝑐}\sum_{i=1}^{𝑐𝑛𝑡_c}{𝑐_𝑖\cdot 𝑤_𝑖}$

其中：$𝑣𝑎𝑙$ 表示该颜色的价值，$𝑐𝑛𝑡$ 表示颜色出现的次数，$𝑤$ 表示该颜色出现 $𝑖$ 次后的价值。

$m$ 次操作：

• 0 x y : 将 $x$ 节点的颜色改为 $y$
• 1 x y : 询问 $x$ 到 $y$ 路径上值

$1 \le n,m,q \le 10^5$

【分析】树上带修莫队

学习完毕

{{ select(1) }}

• YES
• NO