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

5 1 vote
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments