目录
题目链接: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