东莞网站推广软件,湖南营销型网站建设流程,学做烘焙网站,做网站前端用什么软件正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid5709 题目大意 nnn个点的一棵树#xff0c;每次有询问(u,k)(u,k)(u,k)表在uuu的子树中#xff0c;距离uuu不超过kkk的节点中有多少不同颜色的节点。 解题思路
线段树维护每个深度有多少是颜色出现的最浅的位置5709 题目大意
nnn个点的一棵树每次有询问(u,k)(u,k)(u,k)表在uuu的子树中距离uuu不超过kkk的节点中有多少不同颜色的节点。 解题思路
线段树维护每个深度有多少是颜色出现的最浅的位置发现这样无法线段树合并因为每次合并会有多个重复的。所以我们还要再维护一个线段树表示每个颜色第一次出现的位置然后在合并这颗的时候可以把第一课的给去重了。
因为要预处理的是所有的子树的线段树所以每次合并和修改和主席树一样都要新建节点。
时间复杂度O((nq)logn)O((nq)\log n)O((nq)logn) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N5e510,M3e710;
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;xcnt;if(LR)return;int mid(LR)1;if(posmid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid1,R,pos,val);return;}int Ask(int x,int L,int R,int l,int r){if(!x)return 0;if(LlRr)return w[x];int mid(LR)1;if(rmid)return Ask(ls[x],L,mid,l,r);if(lmid)return Ask(rs[x],mid1,R,l,r);return Ask(ls[x],L,mid,l,mid)Ask(rs[x],mid1,R,mid1,r);}int Merge(int x,int y){if(!x||!y)return xy;int nowcnt;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)xcnt,ls[x]rs[x]w[x]0;if(LR){w[x]val;return;}int mid(LR)1;if(posmid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid1,R,pos,val);return;}int Merge(int x,int y,int L,int R,int rt){if(!x||!y)return xy;int nowcnt;if(LR){T1.Change(rt1[rt],1,n,max(w[x],w[y]),-1);w[now]min(w[x],w[y]);return now;}int mid(LR)1;ls[now]Merge(ls[x],ls[y],L,mid,rt);rs[now]Merge(rs[x],rs[y],mid1,R,rt);return now;}
}T2;
void addl(int x,int y){a[tot].toy;a[tot].nextls[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 ils[x];i;ia[i].next){int ya[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.cntT2.cnttot0; scanf(%d%d,n,q);for(int i1;in;i)scanf(%d,c[i]),ls[i]0;for(int i2;in;i){int x;scanf(%d,x);addl(x,i);}dep[1]1;dfs(1);int last0;while(q--){int u,k;scanf(%d%d,u,k);u^last;k^last;printf(%d\n,lastT1.Ask(rt1[u],1,n,dep[u],min(dep[u]k,n)));}}
}
