撰写目录
题目链接：https://www.luogu.org/problem/SP10707 题目概述：给定一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。
区间上有多少个不同的数字？这不就是莫队吗？Rush！
不会。。。莫队是在一个一维序列里进行的算法，这是一棵树啊，怎么办？树上莫队呗，莫队既然要在以为序列里进行运算，那就把这棵树转变成一个一维序列。这里我们要引出一个东西：
欧拉序
顾名思义：欧拉的顺序。欧拉序的核心思想就是在访问到点\(i\)的时候，将\(i\)加入序列，然后访问\(i\)的子树，当访问完\(i\)的子树后，再把\(i\)加入到序列之中。
Four 一个zample:
现在有这样一棵可爱的树，试试写出来他的欧拉序？
它的欧拉序是：
1，2，4，4，3，6，6，3，5，5，2，7，8，8，7，1
我没写错吧？我真的有可能会写错！
学会了欧拉序以后我们就可以把一棵树转化成一维序列啦！莫队开始。
树上莫队
正如全世界都一样的题解一样，我们用两个数组\(s[i]\)和\(t[i]\)来分别记录点\(i\)第一次（扫描其子树前）和第二次（扫描其子树后）的时间点。假设题目中先扫描到点\(x\)，即\(s[x]<s[y]\)，则有如下几种情况：
①\(lca(x,y)=x\)，即\(x\)为\(y\)的祖先（因为前面假设了\(s[x]<s[y]\)），那么\(x,y\)在一条链内，在\(s[x]\)到\(s[y]\)之间时间内，有的点被扫描到两次，有的点没有出现，这都对答案没有影响，只需要统计被扫描到一次的点的数量即可。不明白的话仔细想一想你会发下它的正确性没有问题！
②\(lca(x,y)!=x\)，则此时\(x\)和\(y\)是不在一个子树内的，同样我们按照上面的方法统计\(t[x]\)到\(s[y]\)之间的点。但是别忘了他们的\(lca\)可能没有还没有第二次被加入到序列中，所以要特判！
随后：一根笔，一包烟，一道破题调一天。 //上面这句话是我写这道题之前说的，事实上我应验了这个说法，11:00~16:00
AC代码
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=80010;
const int M=100010;
//数组开够
bool vis[N],used[M];
int l=1,r,n,m,cnt,num,now;
int a[N],b[N],head[N],el[N],be[M],ans[M],deep[N],s[N],t[N],cunt[M];
int f[N][25];
struct edge{
int to,nxt;
}e[N];
struct node{
int l,r,id,lca;
}q[M];
inline int Read(){
int x=0,f=1;
int ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void Add(int x,int y){
cnt++;
e[cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
inline bool CMP(node a,node b){
return (be[a.l]^be[b.l])?be[a.l]<be[b.l]:(be[a.l]&1)?a.r<b.r:a.r>b.r;
}
inline void Addp(int x){
used[x]?now-=!--cunt[a[x]]:now+=!cunt[a[x]]++;
used[x]^=1;
//用一个used数组记录这个位置有没有出现过,每次对这个位置操作后状态都会改变,所以这样子取反是合理的
}
void Euler(int x){
vis[x]=1;
s[x]=++num;
el[num]=x;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]){
f[v][0]=x;
deep[v]=deep[x]+1;
Euler(v);
}
}
t[x]=++num;
el[num]=x;
}
int LCA(int a,int b){
if(deep[a]!=deep[b]){
if(deep[a]<deep[b])
swap(a,b);
for(int i=20;i>=0;i--)
if(deep[f[a][i]]>=deep[b])
a=f[a][i];
}
if(a==b) return a;
for(int i=20;i>=0;i--)
if(f[a][i]!=f[b][i])
a=f[a][i],b=f[b][i];
return f[a][0];
}
int main(){
n=Read();
m=Read();
double sq=sqrt(n);
for(int i=1;i<=(n<<1);i++)
be[i]=i/sq+1;
for(int i=1;i<=n;i++)
b[i]=a[i]=Read();
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;
//这里必须要有离散化处理,要不然cunt数组扛不住,为此我RE了无数次
for(int i=1;i<n;i++){
int x=Read(),y=Read();
Add(x,y);
Add(y,x);
}
deep[1]=1;
Euler(1);
for(int j=1;j<=16;j++)
for(int i=1;i<=n<<1;i++)
f[i][j]=f[f[i][j-1]][j-1];
for(int i=1;i<=m;i++){
int x=Read(),y=Read();
if(s[x]>s[y]) swap(x,y);
q[i].lca=LCA(x,y);
if(q[i].lca==x){
q[i].l=s[x];
q[i].r=s[y];
q[i].lca=0;
}
else{
q[i].l=t[x];
q[i].r=s[y];
}
q[i].id=i;
}
sort(q+1,q+m+1,CMP);
/* for(int i=1;i<=m;i++){
while(l>q[i].l) now+=!cunt[a[el[--l]]]++;
while(l<q[i].l) now-=!--cunt[a[el[l++]]];
while(r<q[i].r) now+=!cunt[a[el[++r]]]++;
while(r>q[i].r) now-=!--cunt[a[el[r--]]];
if(q[i].lca) now+=!cunt[a[q[i].lca]];
ans[q[i].id]=now;
if(q[i].lca) now-=!cunt[a[q[i].lca]];
}*///我不知道为什么但用了常数优化就会错
for(int i=1;i<=m;i++){
while(l<q[i].l) Addp(el[l++]);
while(l>q[i].l) Addp(el[--l]);
while(r<q[i].r) Addp(el[++r]);
while(r>q[i].r) Addp(el[r--]);
if(q[i].lca) Addp(q[i].lca);
ans[q[i].id]=now;
if(q[i].lca) Addp(q[i].lca);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
又一次不计AC率的AC
