树分块

  1 /**************************************************************  2     Problem: 3757  3     User: Tunix  4     Language: C++  5     Result: Accepted  6     Time:17180 ms  7     Memory:17716 kb  8 ****************************************************************/  9   10 //BZOJ 3757 11 #include<cmath> 12 #include<cstdio> 13 #include<cstring> 14 #include<cstdlib> 15 #include<iostream> 16 #include<algorithm> 17 #define rep(i,n) for(int i=0;i<n;++i) 18 #define F(i,j,n) for(int i=j;i<=n;++i) 19 #define D(i,j,n) for(int i=j;i>=n;--i) 20 using namespace std; 21 void read(int &v){ 22     v=0; int sign=1; char ch=getchar(); 23     while(ch<‘0‘||ch>‘9‘){ if (ch==‘-‘) sign=-1; ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){ v=v*10+ch-‘0‘; ch=getchar();} 25     v*=sign; 26 } 27 #define debug 28 /******************tamplate*********************/ 29 const int N=100010; 30 int head[N],to[N],next[N],cnt; 31 void add(int x,int y){ 32     to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt; 33     to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt; 34 } 35 /*******************edge************************/ 36 int n,m,color[N],root; 37 int B,belong[N],st[N],top,tot,deep[N]; 38 int fa[N][20],bin[25]; 39 void dfs(int x){ 40     int bottom=top; 41     for(int i=1;i<=16;i++) 42         if(deep[x]>=bin[i]) 43             fa[x][i]=fa[fa[x][i-1]][i-1]; 44         else break; 45     for(int i=head[x];i;i=next[i]) 46         if (to[i]!=fa[x][0]){ 47             fa[to[i]][0]=x; 48             deep[to[i]]=deep[x]+1; 49             dfs(to[i]); 50             if (top-bottom>=B){ 51                 ++tot; 52                 while(top!=bottom) 53                     belong[st[top--]]=tot; 54             } 55         } 56     st[++top]=x; 57 } 58 int LCA(int x,int y){ 59     if (deep[x]<deep[y]) swap(x,y); 60     int t=deep[x]-deep[y]; 61     for(int i=0;bin[i]<=t;i++) 62         if (t&bin[i]) x=fa[x][i]; 63     D(i,16,0) 64         if(fa[x][i]!=fa[y][i]) 65             x=fa[x][i],y=fa[y][i]; 66     if(x==y) return x; 67     return fa[x][0]; 68 } 69 /*******************dfs&&LCA********************/ 70 struct ques{ 71     int x,y,a,b,num; 72     bool operator < (const ques &now)const{ 73         if (belong[x]==belong[now.x]) return belong[y]<belong[now.y]; 74         else return belong[x]<belong[now.x]; 75     } 76 }Q[N]; 77   78 int num[N],ans=0,ANS[N]; 79 bool used[N]; 80 inline void work(int x){ 81     if(!used[x]){ 82         num[color[x]]++;used[x]=1; 83         if(num[color[x]]==1) ans++; 84     } 85     else{ 86         num[color[x]]--;used[x]=0; 87         if(num[color[x]]==0) ans--; 88     } 89 } 90   91 void Xor(int x,int y){ 92     int lca=LCA(x,y); 93     while(x!=lca) {work(x); x=fa[x][0];} 94     while(y!=lca) {work(y); y=fa[y][0];} 95 } 96   97 int main(){ 98     bin[0]=1; F(i,1,20) bin[i]=bin[i-1]<<1; 99  100     read(n); read(m);101     B=sqrt(n);102     F(i,1,n) read(color[i]);103     int x,y;104     F(i,1,n){105         read(x); read(y);106         if (x==0) root=y;107         if (y==0) root=x;108         add(x,y);109     }110     dfs(root);111     tot++;112     while(top)belong[st[top--]]=tot;113  114     int a,b;115     F(i,1,m){116         read(x); read(y); read(a); read(b);117         Q[i]=(ques){x,y,a,b,i};118     }119     sort(Q+1,Q+m+1);120     //转移的时候不考虑LCA，查答案的时候临时算进来，计算完答案后再把LCA删掉121     int lca=(LCA(Q[1].x,Q[1].y));122     Xor(Q[1].x,Q[1].y);123     work(lca);124     ANS[Q[1].num]=ans;125     if (num[Q[1].a]!=0 && num[Q[1].b]!=0 && Q[1].a!=Q[1].b) ANS[Q[1].num]--;126     work(lca);127     F(i,2,m){128         Xor(Q[i-1].x,Q[i].x);129         Xor(Q[i-1].y,Q[i].y);130         lca=LCA(Q[i].x,Q[i].y);131         work(lca);132         ANS[Q[i].num]=ans;133         if(num[Q[i].a]!=0 && num[Q[i].b]!=0 && Q[i].a!=Q[i].b) ANS[Q[i].num]--;134         work(lca);135     }136     F(i,1,m) printf("%d\n",ANS[i]);137     return 0;138 }