首页 > 代码库 > 【线段树】CSU 1414 Query on a Tree
【线段树】CSU 1414 Query on a Tree
点击打开链接
线段树新功能get,太神奇了啊@-@
先遍历下树,时间戳记录下前后时间
子节点的前后时间都会在父节点的前后时间范围内
用线段树维护区间内深度最大和深度最小
#include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <cmath> using namespace std; #include <queue> #include <stack> #include <set> #include <vector> #include <deque> #include <map> #define cler(arr, val) memset(arr, val, sizeof(arr)) #pragma comment(linker, "/STACK:102400000,102400000") typedef long long LL; const int MAXN = 102020; const int MAXM = 240000; const int INF = 0x3f3f3f3f; const int mod = 1000000007; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int ti,maxx[MAXN<<2],minn[MAXN<<2],head[MAXN],tol,deep[MAXN]; struct node { int v,next; }edge[MAXM]; struct node1 { int t1,t2; }tt[MAXN]; void init() { cler(head,-1);tol=0;ti=0; } void addedge(int u,int v) { edge[tol].v=v;edge[tol].next=head[u];head[u]=tol++; } void dfs(int u,int dep) { deep[ti]=dep; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].v; tt[v].t1=++ti; dfs(v,dep+1); tt[v].t2=ti; } } void dfs1(int u,int dep) { tt[u].t1=++ti; deep[ti]=dep; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].v; dfs1(v,dep+1); } tt[u].t2=ti; } void pushup(int rt) { maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]); minn[rt]=min(minn[rt<<1],minn[rt<<1|1]); } void build(int l,int r,int rt) { if(l==r) { maxx[rt]=minn[rt]=deep[l]; return ; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } int query(int L,int R,int bb,int mm,int l,int r,int rt) { if(L<=l&&r<=R&&maxx[rt]<=mm&&minn[rt]>=bb) { return r-l+1; } else if(minn[rt]>mm) return 0; else if(maxx[rt]<bb) return 0; int m=(l+r)>>1; int ans=0; if(L<=m) ans+=query(L,R,bb,mm,lson); if(R>m) ans+=query(L,R,bb,mm,rson); return ans; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif int t,n,v,m,x,d; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); for(int i=2;i<=n;i++) { scanf("%d",&v); addedge(v,i); } ti=0; dfs1(1,0); build(1,n,1); scanf("%d",&m); while(m--) { scanf("%d%d",&x,&d); int ans=query(tt[x].t1,tt[x].t2,deep[tt[x].t1],deep[tt[x].t1]+d-1,1,n,1); printf("%d\n",ans); } } return 0; }
【线段树】CSU 1414 Query on a Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。