Prutekoi's blog

这样一个问题

给定一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。

第一眼看起来像是HH的项链搬到树上,于是想到把树摊到序列上离线把询问排序。可是这道题问的是两点之间路径。对于路径我们的处理办法一般是树上差分,可是这个信息又不支持可减性,于是基本可以叉掉这个做法了...

据说lxl证过这个问题没有$O(n\ polylog)$的做法,于是我们就要想暴力啦

对于HH的项链还有一个莫队的做法,那么我们是否可以把莫队搬到树上?

答案是可以的...我们要将树用括号序摊成序列,然后分两类讨论一下。
记$x$入栈的位置为$op[x]$,出栈的位置为$ed[x]$
令$op[x]<=p[y]$。
若$x$是$y$的祖先($ed[x]\geq ed[y]$),即$x$到$y$是直上直下一条链,那么$[st[x],st[y]]$这个区间内$x$到$y$路径上的点都出现了1次,其他点要么出现两次要么没出现。(括号序就是模拟进退栈,考虑dfs的过程,是显然的)

若$x$不是$y$的祖先,那么路径构成$x$到$lca$上,$lca$到$y$下两部分。
$[ed[x],st[y]]$区间内除了$lca$以外的路径上的点都出现1次。那么特判$lca$即可。

所以我们在序列上莫队,记录每个点在区间内出现次数的奇偶性,直接维护即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n,q,a[N],ver[N*2],nxt[N*2],head[N],tot,f[N][16],d[N],op[N],ed[N],cnt,sq,bel[N],ans[N],b[N],c[N],m,num[N],now,k[N];
struct node{int l,r,id,op;bool friend operator <(node a,node b){return bel[a.l]!=bel[b.l]?a.l<b.l:a.r<b.r;}}Q[N];
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void dfs(int x,int ff){
	f[x][0]=ff;b[op[x]=++cnt]=x;d[x]=d[ff]+1;
	for(int i=0;i<15;i++)f[x][i+1]=f[f[x][i]][i];
	for(int i=head[x],y;i;i=nxt[i])
		if((y=ver[i])!=ff)dfs(y,x);
	b[ed[x]=++cnt]=x;
}
int lca(int x,int y){
	if(d[x]<d[y])swap(x,y);
	for(int i=15;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
	if(x==y)return x;
	for(int i=15;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
void change(int x){k[x]^=1,k[x]?!num[a[x]]++&&now++:!--num[a[x]]&&now--;}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),c[i]=a[i];
	sort(c+1,c+n+1);m=unique(c+1,c+n+1)-c-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(c+1,c+m+1,a[i])-c;
	for(int i=1,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);sq=sqrt(2*n);
	for(int i=1;i<=2*n;i++)bel[i]=(i-1)/sq+1;
	for(int i=1,x,y;i<=q;i++){
		scanf("%d%d",&x,&y);
		if(op[x]>op[y])swap(x,y);
		if(ed[x]>=ed[y])Q[i]=(node){op[x],op[y],i,0};
		else Q[i]=(node){ed[x],op[y],i,1};
	}
	sort(Q+1,Q+q+1);
	for(int i=1,l=1,r=0;i<=q;i++){
		int L=Q[i].l,R=Q[i].r;
		while(r<R)change(b[++r]);
		while(l>L)change(b[--l]);
		while(r>R)change(b[r--]);
		while(l<L)change(b[l++]);
		ans[Q[i].id]=now+(Q[i].op&&!num[a[lca(b[L],b[R])]]);
	}
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
}

这道题还有强制在线版本,要树分块,咕咕咕

如果是查子树的话就更好写了...直接dfs序即可。。甚至可以dsu on tree变成nlogn