首页 > 代码库 > 【树上莫队】bzoj3757 苹果树

【树上莫队】bzoj3757 苹果树

2024-11-16 05:48:01   202人阅读

学习这位神犇的：http://blog.csdn.net/jiangyuze831/article/details/41476865

注意：

①排序时第一关键字是左端点所在块编号(块状树)，第二关键字是右端点dfs序。

②维护的当前链不能包括lca(l,r)，但最后要计算上lca(l,r)的答案。

③对l->l‘/r->r‘取反的时候也不能取反lca(l,l‘)/lca(r,r‘)。

#include<cstdio>#include<cmath>#include<algorithm>using namespace std;#define N 50001#define M 100001int n,m;int first[N],en,next[N<<1],dfsn[N],v[N<<1],fa[N],bel[N],dep[N],siz[N],cnt,top[N];int x,y,root,sz,col[N],Time[N],ans,anss[M];bool vis[N];struct ASK{int l,r,a,b,id;void Read(){scanf("%d%d%d%d",&l,&r,&a,&b);}}Q[M];bool operator < (const ASK &a,const ASK &b){return bel[a.l]!=bel[b.l] ? bel[a.l]<bel[b.l] : dfsn[a.r]<dfsn[b.r];}void AddEdge(const int &U,const int &V){	v[++en]=V;	next[en]=first[U];	first[U]=en;}void dfs(int cur){	dfsn[cur]=++cnt;	for(int i=first[cur];i;i=next[i])	  if(v[i]!=fa[cur])	    {	      dep[v[i]]=dep[cur]+1;          fa[v[i]]=cur;          dfs(v[i]);	    }}void makeblock(int cur){    for(int i=first[cur];i;i=next[i])      if(v[i]!=fa[cur])        {          if(siz[bel[cur]]<sz)            {              ++siz[bel[cur]];              bel[v[i]]=bel[cur];              top[v[i]]=top[cur];            }          makeblock(v[i]);        }}int QLCA(int U,int V){    while(U!=V)      {        if(top[U]==top[V])          {            if(dep[U]<dep[V])			  swap(U,V);            U=fa[U];          }        else          {            if(dep[top[U]]<dep[top[V]])			  swap(U,V);            U=fa[top[U]];          }      }    return U;}void update(const int &Col,const int &op){	Time[Col]+=op;	if(!Time[Col]) --ans;	else if(Time[Col]==1&&op==1) ++ans;}void Work(int U,int V,int lca)  {	while(U!=lca)	  {        vis[U]^=1;	  	update(col[U],vis[U]?1:-1);        U=fa[U];	  }	while(V!=lca)	  {        vis[V]^=1;	  	update(col[V],vis[V]?1:-1);        V=fa[V];	  }}  void Solve(const int &p)  {    int lca=QLCA(Q[p].l,Q[p].r);    if(p==1) Work(Q[p].l,Q[p].r,lca);    else      {      	Work(Q[p-1].l,Q[p].l,QLCA(Q[p-1].l,Q[p].l));      	Work(Q[p-1].r,Q[p].r,QLCA(Q[p-1].r,Q[p].r));      }    update(col[lca],1);    anss[Q[p].id]=ans;    if(Q[p].a!=Q[p].b)      anss[Q[p].id]-=(Time[Q[p].a]&&Time[Q[p].b]);    update(col[lca],-1);}  int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;++i) scanf("%d",&col[i]);	for(int i=1;i<=n;++i)	  {	  	scanf("%d%d",&x,&y);	  	if(!x) root=y;	  	else if(!y) root=x;	  	else	  	  {	  	  	AddEdge(x,y);	  	  	AddEdge(y,x);	  	  }	  }	dfs(root);	for(int i=1;i<=n;i++)	  {	  	siz[bel[i]=dfsn[i]]=1;	    top[i]=i;	  }	sz=(((int)sqrt(n))<<1);	makeblock(root);	for(int i=1;i<=m;++i) Q[i].Read(),Q[i].id=i;	sort(Q+1,Q+m+1);	for(int i=1;i<=m;++i) Solve(i);	for(int i=1;i<=m;++i) printf("%d\n",anss[i]);	return 0;}

【树上莫队】bzoj3757 苹果树


联系
我们