正題

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=5709

---

題目大意

$n$個(gè)點(diǎn)的一棵樹，每次有詢問$(u,k)$表在$u$的子樹中，距離$u$不超過$k$的節(jié)點(diǎn)中有多少不同顏色的節(jié)點(diǎn)。

---

解題思路

線段樹維護(hù)每個(gè)深度有多少是顏色出現(xiàn)的最淺的位置，發(fā)現(xiàn)這樣無法線段樹合并，因?yàn)槊看魏喜卸鄠€(gè)重復(fù)的。所以我們還要再維護(hù)一個(gè)線段樹表示每個(gè)顏色第一次出現(xiàn)的位置，然后在合并這顆的時(shí)候可以把第一課的給去重了。

因?yàn)橐A(yù)處理的是所有的子樹的線段樹，所以每次合并和修改（和主席樹一樣）都要新建節(jié)點(diǎn)。

時(shí)間復(fù)雜度$O((n+q)\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=5e5+10,M=3e7+10; struct node{int to,next; }a[N]; int T,n,q,c[N],dep[N],ls[N],rt1[N],rt2[N],tot; struct Seq_Tree1{int cnt,ls[M],rs[M],w[M];void Change(int &x,int L,int R,int pos,int val){++cnt;ls[cnt]=ls[x];rs[cnt]=rs[x];w[cnt]=w[x]+val;x=cnt;if(L==R)return;int mid=(L+R)>>1;if(pos<=mid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid+1,R,pos,val);return;}int Ask(int x,int L,int R,int l,int r){if(!x)return 0;if(L==l&&R==r)return w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],L,mid,l,r);if(l>mid)return Ask(rs[x],mid+1,R,l,r);return Ask(ls[x],L,mid,l,mid)+Ask(rs[x],mid+1,R,mid+1,r);}int Merge(int x,int y){if(!x||!y)return x+y;int now=++cnt;w[now]=w[x]+w[y];ls[now]=Merge(ls[x],ls[y]);rs[now]=Merge(rs[x],rs[y]);return now;} }T1; struct Seq_Tree2{int cnt,ls[M],rs[M],w[M];void Change(int &x,int L,int R,int pos,int val){if(!x)x=++cnt,ls[x]=rs[x]=w[x]=0;if(L==R){w[x]=val;return;}int mid=(L+R)>>1;if(pos<=mid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid+1,R,pos,val);return;}int Merge(int x,int y,int L,int R,int rt){if(!x||!y)return x+y;int now=++cnt;if(L==R){T1.Change(rt1[rt],1,n,max(w[x],w[y]),-1);w[now]=min(w[x],w[y]);return now;}int mid=(L+R)>>1;ls[now]=Merge(ls[x],ls[y],L,mid,rt);rs[now]=Merge(rs[x],rs[y],mid+1,R,rt);return now;} }T2; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x){rt1[x]=rt2[x]=0;T1.Change(rt1[x],1,n,dep[x],1);T2.Change(rt2[x],1,n,c[x],dep[x]); for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dep[y]=dep[x]+1;dfs(y);rt1[x]=T1.Merge(rt1[x],rt1[y]);rt2[x]=T2.Merge(rt2[x],rt2[y],1,n,x);}return; } int main() {scanf("%d",&T);while(T--){T1.cnt=T2.cnt=tot=0; scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%d",&c[i]),ls[i]=0;for(int i=2;i<=n;i++){int x;scanf("%d",&x);addl(x,i);}dep[1]=1;dfs(1);int last=0;while(q--){int u,k;scanf("%d%d",&u,&k);u^=last;k^=last;printf("%d\n",last=T1.Ask(rt1[u],1,n,dep[u],min(dep[u]+k,n)));}} }

總結(jié)

以上是生活随笔為你收集整理的hdu5709-Claris Loves Painting【线段树合并】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。