题意：
给出一颗结点为n的树，每个结点有种颜色；
m次查询两个结点之间路径颜色种类数；
n<=50000，m<=100000；
询问可能要求将某两种颜色视为一种；
题解：
裸的树上莫队，似乎很神的一种做法。。
首先将树分块，块大小B=sqrt(n)；
具体树的分块方法见大爷的博客：手把手教你块状树系列
分块之后将询问排序，第一关键字按l结点所在块，第二关键字按r结点的DFS序；
然后处理如何从l到r的路径转移到l'到r的路径；
首先莫队算法其实是对一个集合的维护，记录的数组是l到r路径上点的集合；
那么根据VFleaKing的证明，我们可以维护l到r路径上不包括LCA(l,r)的点集；
转移直接将l到l'路径上的所有点是否在集合中的状态取反就可以了；
时间复杂度和区间上的复杂度类似，都是O(n√n)；
但是常数应该是大一些，因为块状树要深搜，LCA要一个log(这个是倍增，似乎不能用tarjan解决吧)
代码：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 51000
using namespace std;
struct node
{
int l,r,pos,tim,a,b,no;
}Q[N<<1];
int to[N<<1],next[N<<1],head[N];
int st[N],belong[N],deep[N],dt[N],fa[N][20];
int a[N],s[N],ans[N<<1];
int ce,top,bk,tot,cnt,now;
bool vis[N];
bool cmp(node a,node b)
{
if(a.pos==b.pos)
return a.tim<b.tim;
return a.pos<b.pos;
}
void add(int x,int y)
{
to[++ce]=y;
next[ce]=head[x];
head[x]=ce;
}
void dfs(int x,int pre,int d)
{
deep[x]=d;
dt[x]=++cnt;
fa[x][0]=pre;
int i,y,b=top;
for(i=head[x];i;i=next[i])
{
if((y=to[i])!=pre)
{
dfs(y,x,d+1);
if(top-b>=bk)
{
tot++;
while(top>b)
belong[st[top--]]=tot;
}
}
}
st[++top]=x;
}
int Lca(int x,int y)
{
while(deep[x]!=deep[y])
{
if(deep[x]<deep[y])
swap(x,y);
int k=log2(deep[x]-deep[y]);
x=fa[x][k];
}
if(x==y) return x;
int k=log2(deep[x]);
while(k>=0)
{
if(fa[x][k]!=fa[y][k])
x=fa[x][k],y=fa[y][k];
k--;
}
return fa[x][0];
}
void update(int x,int g)
{
while(x!=g)
{
if(!s[a[x]])
now++;
s[a[x]]+=(vis[x]?-1:1);
vis[x]=!vis[x];
if(!s[a[x]])
now--;
x=fa[x][0];
}
}
int main()
{
int n,m,i,j,k,l,r,x,y,root;
scanf("%d%d",&n,&m);
bk=sqrt(n)*2;
for(i=1;i<=n;i++)
scanf("%d",a+i);
for(i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if(!x||!y)
root=x?x:y;
else
add(x,y),add(y,x);
}
dfs(root,0,0);
while(top)
belong[st[top--]]=tot;
for(k=1;(1<<k)<=n;k++)
for(i=1;i<=n;i++)
fa[i][k]=fa[fa[i][k-1]][k-1];
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&Q[i].l,&Q[i].r,&Q[i].a,&Q[i].b);
if(belong[Q[i].l]>belong[Q[i].r]) swap(Q[i].l,Q[i].r);
Q[i].pos=belong[Q[i].l],Q[i].tim=dt[Q[i].r];
Q[i].no=i;
if(Q[i].a==Q[i].b)
Q[i].a=Q[i].b=n+1;
}
sort(Q+1,Q+m+1,cmp);
l=1,r=1;
for(i=1;i<=m;i++)
{
x=Lca(Q[i].l,l);
update(Q[i].l,x);
update(l,x);
x=Lca(Q[i].r,r);
update(Q[i].r,x);
update(r,x);
x=Lca(Q[i].l,Q[i].r);
update(x,fa[x][0]);
ans[Q[i].no]=(s[Q[i].a]&&s[Q[i].b]?now-1:now);
update(x,fa[x][0]);
l=Q[i].l,r=Q[i].r;
}
for(i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
|
转播
