正題

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

---

題目大意

給出$n$個點的一棵樹，每個節點有一個顏色，$m$次詢問提出區間$[l,r]$的點構成的生成子圖中$x$所在連通塊的顏色數。

$1\le n,m,a_i\le 10^5$

---

解題思路

用點分樹解決本題是很妙的想法。/bx

考慮點分樹如何解決，對于一個詢問$l,r,x$，如果$x$在點分樹上的一個祖先$y$滿足$x$到$y$的路徑都是$[l,r]$的點，那么此時在$y$的點分子樹上的所有節點$z$都滿足如果$y$到$z$的路徑都是$[l,r]$的節點，那么$x$到$z$的也是。具體原因很好理解，因為兩條路徑重復的那一段路已經滿足條件了。

那么我們此時就可以將一個條件拆分成兩個條件掛在$y$上了，具體地我們對于每個詢問找到$x$點分樹上深度最小的祖先$y$滿足$x$到$y$的路徑上都是$[l,r]$的節點，然后把這個詢問掛在這個點上。

然后我們暴力枚舉所有點然后處理它的點分樹子樹，假設現在枚舉到$x$點，我們把它的所有兒子按照$x$到它們的路徑上的最小值從大到小詢問，然后掛在$x$點上的詢問按照$l$從大到小排序。

然后暴力遍歷，記錄每個顏色最小的$mx$表示$y$到這個顏色的點需要經過的路徑最大值，然后把權值丟到樹狀數組上查詢即可。

時間復雜度：$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define lowbit(x) (x&-x) using namespace std; const int N=1e5+10; struct edge{int to,next; }a[N<<1]; struct node{int x,fa,l,r; }; int n,m,tot,num,root,ls[N],c[N]; int siz[N],f[N],t[N],lat[N],ans[N]; vector<node> anc[N],son[N],q[N]; bool v[N]; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void Groot(int x,int fa){siz[x]=1;f[x]=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||v[y])continue;Groot(y,x);siz[x]+=siz[y];f[x]=max(f[x],siz[y]);}f[x]=max(f[x],num-siz[x]);if(f[x]<f[root])root=x;return; } void dfs(int x,int fa,int fr,int mi=1e9,int mx=-1e9){mi=min(x,mi);mx=max(x,mx);anc[x].push_back((node){x,fr,mi,mx});son[fr].push_back((node){x,fr,mi,mx});for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||v[y])continue;dfs(y,x,fr,mi,mx);}return; } void Build(int x){int S=num;v[x]=1;dfs(x,0,x);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y])continue;num=(siz[y]>siz[x])?(S-siz[x]):siz[y];root=0;Groot(y,x);Build(root);}return; } bool cmp(node x,node y) {return x.l>y.l;} void Change(int x,int val){while(x<=n){t[x]+=val;x+=lowbit(x);}return; } int Ask(int x){int ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&c[i]);for(int i=1;i<n;i++){int x,y;x=i,y=i+1;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}f[0]=n+1;num=n;Groot(1,1);Build(root);for(int t=1;t<=m;t++){int l,r,x;scanf("%d%d%d",&l,&r,&x);for(int i=0;i<anc[x].size();i++)if(anc[x][i].l>=l&&anc[x][i].r<=r){q[anc[x][i].fa].push_back((node){x,t,l,r});break;}}for(int i=0;i<N;i++)lat[i]=n+1;for(int p=1;p<=n;p++){sort(q[p].begin(),q[p].end(),cmp);sort(son[p].begin(),son[p].end(),cmp);int z=0;for(int i=0;i<son[p].size();i++){node x=son[p][i];while(z<q[p].size()&&q[p][z].l>x.l){node y=q[p][z];ans[y.fa]=Ask(y.r);z++;}Change(lat[c[x.x]],-1);lat[c[x.x]]=min(lat[c[x.x]],x.r);Change(lat[c[x.x]],1);}while(z<q[p].size()){node y=q[p][z];ans[y.fa]=Ask(y.r);z++;}for(int i=0;i<son[p].size();i++){node x=son[p][i];Change(lat[c[x.x]],-1);lat[c[x.x]]=n+1;}}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的P5311-[Ynoi2011]成都七中【点分树,树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

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