题目大意
给出一棵树,每个点有点权,询问两点之间的路径有多少种不同的权值。
解题思路
观察可知,一般的算法无法解决这个问题,我们考虑传说中的暴力算法莫队算法。求出dfs序,将左端点按sqrt(n)一块分块为第一关键字,将右端点为第二关键字排序。可以发现这样做之后左端点每次不会移动超过sqrt(n)位,而右端点会被分成sqrt(n)个单调序列,每个序列移动不会超过n,这样我们就可以在n sqrt(n)解决这个问题。
我们考虑将一段路径的一个端点移到另一个端点,我们发现我们可以将前后端点间的路径上的点存在性取反,但是交点会被我们忽略,我们发现交点会在原路径交点,改后的交点和两个交点路径交点之间。我们可以比较它们之间的深度发现那一个是实际交点。
code
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define Min(a,b) ((a<b)?a:b)
#define Max(a,b) ((a>b)?a:b)
#define Fo(i,j,k) for(int i=j;i<=k;i++)
#define Fd(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
int const MxN=4*1e4,MxM=1e5;
int N,M,Edge,Time,Size,Mx,Mo,Kind,Ha[MxN+9],Cnt[MxN+9],Ans[MxM+9],A[MxN+9],Tag[MxN+9],Dfn[MxN+9],Begin[MxN+9],Dep[MxN+9],Fa[MxN+9][17],To[MxN*2+9],Next[MxN*2+9];
struct Rec{int U,V,P;};
Rec Q[MxM+9];
void Insert(int U,int V){
To[++Edge]=V;
Next[Edge]=Begin[U];
Begin[U]=Edge;
}
void Dfs(int Now,int Pre){
Dfn[Now]=++Time;
Dep[Now]=Dep[Pre]+1;
for(int i=Begin[Now];i;i=Next[i])if(To[i]!=Pre)Fa[To[i]][0]=Now,Dfs(To[i],Now);
}
int Lc(int U,int V){
if(Dep[U]<Dep[V])swap(U,V);
Fd(i,Mx,0)if(Dep[Fa[U][i]]>=Dep[V])U=Fa[U][i];
if(U==V)return U;
Fd(i,Mx,0)if(Fa[U][i]!=Fa[V][i])U=Fa[U][i],V=Fa[V][i];
return Fa[U][0];
}
bool Cmp(Rec X,Rec Y){
return (Dfn[X.U]/Size<Dfn[Y.U]/Size)||((Dfn[X.U]/Size==Dfn[Y.U]/Size)&&(Dfn[X.V]<Dfn[Y.V]));
}
int Hash(int X){
int P=X%Mo;
while(Ha[P]&&(Ha[P]!=X))P=(P+1)%Mo;
return P;
}
void Oper2(int U){
int P=Hash(A[U]);Ha[P]=A[U];
Kind-=(Cnt[P]==1)&&(Tag[U]==-1);
Kind+=(Cnt[P]==0)&&(Tag[U]==1);
Cnt[P]+=Tag[U];
Tag[U]=-Tag[U];
}
void Oper3(int U,int V){
while(U!=V){
Oper2(U);
U=Fa[U][0];
}
}
void Oper(int U,int V){
int Lca=Lc(U,V);
Oper3(U,Lca);
Oper3(V,Lca);
Oper2(Lca);
}
int main(){
//freopen("d.in","r",stdin);
//freopen("d.out","w",stdout);
scanf("%d%d",&N,&M);
Size=sqrt(N);Mo=N;Mx=log(N)/log(2);
Fo(i,1,N)scanf("%d",&A[i]),A[i]++,Tag[i]=1;
int U,V;
Fo(i,2,N){
scanf("%d%d",&U,&V);
Insert(U,V);Insert(V,U);
}
Dfs(1,0);int K,Lca;
Fo(j,1,Mx)Fo(i,1,N)Fa[i][j]=Fa[Fa[i][j-1]][j-1];
Fo(i,1,M)scanf("%d%d",&Q[i].U,&Q[i].V),Q[i].P=i;
sort(Q+1,Q+M+1,Cmp);
Oper(Q[1].U,Q[1].V);Ans[Q[1].P]=Kind;
Fo(i,2,M){
Oper(Q[i-1].U,Q[i].U);
int Lca1=Lc(Q[i-1].U,Q[i-1].V),Lca2=Lc(Q[i-1].U,Q[i].U),Lca3=Lc(Q[i-1].V,Q[i].U);
if(Dep[Lca2]<Dep[Lca3])Lca2=Lca3;
if(Dep[Lca1]>Dep[Lca2]){
if(Tag[Lca1]==1)Oper2(Lca1);
}else{
if(Tag[Lca2]==1)Oper2(Lca2);
}
if(Tag[Q[i].U]==1)Oper2(Q[i].U);
Oper(Q[i-1].V,Q[i].V);
Lca1=Lc(Q[i].U,Q[i-1].V),Lca2=Lc(Q[i-1].V,Q[i].V),Lca3=Lc(Q[i].U,Q[i].V);
if(Dep[Lca2]<Dep[Lca3])Lca2=Lca3;
if(Dep[Lca1]>Dep[Lca2]){
if(Tag[Lca1]==1)Oper2(Lca1);
}else{
if(Tag[Lca2]==1)Oper2(Lca2);
}
if(Tag[Q[i].V]==1)Oper2(Q[i].V);
Ans[Q[i].P]=Kind;
if(Q[i].U==Q[i].V)Ans[Q[i].P]=1;
}
Fo(i,1,M)printf("%d\n",Ans[i]);
return 0;
}