正題

題目鏈接:https://www.luogu.com.cn/problem/P6177

---

題目大意

$n$個點的一棵樹$m$次詢問樹上顏色。
強制在線

$1\le n\le 4\times 10^5,1\le m\le 10^5,0\le va{l}_i<2^{31}$

---

解題思路

把所有深度為$\sqrt{n}$并且下面至少有$\sqrt{n}$的深度的點標記，這樣保證關鍵點數量不超過$\sqrt{n}$。

然后每個點到他周圍關鍵點的距離也不會超過 $\sqrt{n}$ 。

這樣可以處理出關鍵點兩兩之間的顏色$bitset$，然后每次路徑找兩個最近的關鍵點爆做就好了。

時間復雜度$O((m+n)(\sqrt{n}+\frac{n}{\omega }))$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<bitset> #include<cmath> using namespace std; const int N=41000,T=300,M=(4e4)/T+10; struct node{int to,next; }a[N<<1]; int n,m,tot,cnt,sum,fa[N],v[N],top[N],ls[N],d[N],dep[N],w[N],b[N],mark[N],dfn[N],ed[N],g[M][M]; bitset<N> f[M][M],bt; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x])continue;dep[y]=dep[x]+1;fa[y]=x;dfs(y);d[x]=max(d[x],d[y]+1);}if(dep[x]%T==0&&d[x]>=T)mark[x]=++cnt;return; } void dFs(int x){if(mark[x])top[x]=x;dfn[x]=++cnt;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa[x])continue;top[y]=top[x];dFs(y);}ed[x]=cnt;return; } void calc(int x,int p,int fa){if(!v[w[x]])bt[w[x]]=1,sum++;v[w[x]]++;if(mark[x])f[p][mark[x]]=bt,g[p][mark[x]]=sum;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;calc(y,p,x);}v[w[x]]--;if(!v[w[x]])bt[w[x]]=0,sum--;return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&w[i]),b[i]=w[i];sort(b+1,b+1+n);int L=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++)w[i]=lower_bound(b+1,b+1+L,w[i])-b;for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dfs(1);cnt=0;dFs(1);for(int i=1;i<=n;i++)if(mark[i])calc(i,mark[i],i);int last=0;while(m--){int x,y;scanf("%d%d",&x,&y);x^=last;if(top[x]==top[y]){int xx=x,yy=y,ans=0;while(x!=y){if(dep[x]<dep[y])swap(x,y);if(!v[w[x]])ans++,v[w[x]]=1;x=fa[x];}if(!v[w[x]])ans++,v[w[x]]=1;printf("%d\n",ans);last=ans;x=xx;y=yy;while(x!=y){if(dep[x]<dep[y])swap(x,y);v[w[x]]=0;x=fa[x];}v[w[x]]=0;}else{if(dfn[x]>=dfn[y]&&dfn[x]<=ed[y])swap(x,y);if(dfn[y]>=dfn[x]&&dfn[y]<=ed[x]){int z=top[y];while(top[fa[z]]!=top[x])z=top[fa[z]];bt=f[mark[z]][mark[top[y]]];int ans=g[mark[z]][mark[top[y]]];while(y!=top[y]){if(!bt[w[y]])ans++,bt[w[y]]=1;y=fa[y];}while(z!=x){if(!bt[w[z]])ans++,bt[w[z]]=1;z=fa[z];}if(!bt[w[z]])ans++,bt[w[z]]=1;printf("%d\n",ans);last=ans;}else{bt=f[mark[top[x]]][mark[top[y]]];int ans=g[mark[top[x]]][mark[top[y]]];while(x!=top[x]){if(!bt[w[x]])ans++,bt[w[x]]=1;x=fa[x];}while(y!=top[y]){if(!bt[w[y]])ans++,bt[w[y]]=1;y=fa[y];}printf("%d\n",ans);last=ans;}}}return 0; }

總結

以上是生活随笔為你收集整理的P6177-Count on a tree II/[模板]树分块的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。