BZOJ3757 : 苹果树

时间：2021-10-29 14:38:03

树上莫队，有几个坑：

  1. a可能等于b

  2. 数据范围是100000

#include<cstdio>

#include<algorithm>

#include<cmath>

#define N 100010

#define K 17

using namespace std;

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

struct P{int l,r,z,a,b,id;}Q[N];

int lim,pos[N<<1],l,r,c[N],g[N],v[N<<1],nxt[N<<1],ed,n,m,i,j,x,y,z,loc[N<<1],dfn,st[N],en[N],d[N],f[N][18],ans[N],cnt[N],sum;bool vis[N];char ch;

inline bool cmp(P a,P b){return pos[a.l]<pos[b.l]||pos[a.l]==pos[b.l]&&a.r<b.r;}

inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}

void dfs(int x){

  for(int i=vis[loc[st[x]=++dfn]=x]=1;i<=K;i++)f[x][i]=f[f[x][i-1]][i-1];

  for(int i=g[x];i;i=nxt[i])if(!vis[v[i]])d[v[i]]=d[f[v[i]][0]=x]+1,dfs(v[i]);

  loc[en[x]=++dfn]=x;

}

inline int lca(int x,int y){

  if(x==y)return x;

  if(d[x]<d[y])swap(x,y);

  for(int i=K;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];

  if(x==y)return x;

  for(int i=K;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

  return f[x][0];

}

inline void deal(int x){

  if(!vis[x]){if(!(--cnt[c[x]]))sum--;}else if(!(cnt[c[x]]++))sum++;

  vis[x]^=1;

}

int main(){

  for(read(n),read(m),i=1;i<=n;i++)read(c[i]);

  for(i=1;i<=n;i++){

    read(x),read(y);

    if(x*y)add(x,y),add(y,x);

  }

  for(dfs(d[1]=1),lim=(int)sqrt(n*2+0.5),i=1;i<=dfn;i++)pos[i]=(i-1)/lim+1;

  for(i=1;i<=m;i++){

    read(x),read(y),read(Q[i].a),read(Q[i].b);Q[i].id=i;

    if(st[x]>st[y])swap(x,y);

    z=lca(x,y);

    if(z==x)Q[i].l=st[x],Q[i].r=st[y];else Q[i].l=en[x],Q[i].r=st[y],Q[i].z=z;

  }

  for(sort(Q+1,Q+m+1,cmp),i=1,l=1,r=0;i<=m;i++){

    if(r<Q[i].r){for(r++;r<=Q[i].r;r++)deal(loc[r]);r--;}

    if(r>Q[i].r)for(;r>Q[i].r;r--)deal(loc[r]);

    if(l<Q[i].l)for(;l<Q[i].l;l++)deal(loc[l]);

    else if(l>Q[i].l){for(l--;l>=Q[i].l;l--)deal(loc[l]);l++;}

    if(Q[i].z)deal(Q[i].z);

    ans[Q[i].id]=sum-(Q[i].a!=Q[i].b&&cnt[Q[i].a]&&cnt[Q[i].b]);

    if(Q[i].z)deal(Q[i].z);

  }

  for(i=1;i<=m;i++)printf("%d\n",ans[i]);

  return 0;

}

　　

相关文章