题意
给你一棵树,要你实现两个操作,且强制在线。
- 在新建一个节点链接到原有节点。
- 查询当前节点 到根节点有多少个值大于等于 的,且路径长度小于一定值 。
分析
如果我们暴力求解。那么插入节点的时间复杂度为 ,查询操作的时间复杂度为 。考虑平衡时间复杂度。因为是没有修改操作的,那么当插入一个节点之后这个节点到根节点的路径就确定了。考虑优化暴力走父亲的过程。定义 是节点 的应该走的第 节点, 是 到 的路径长度。那么只需要在插入一个节点时更新它的倍增数组就好了,时间复杂度 。查询的复杂度为 。讨论一下定值 和 的关系就好了。代码
#include<bits/stdc++.h> using namespace std; #define LL long long LL read() { LL x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return f?-x:x; } const LL N = 4e5+100,inf = 0x3f3f3f3f3f3f3f3f; LL val[N],fa[N][21],s[N][21],si = 1,ans = 0,Q; void add(LL x,LL f) { if(val[f] >= val[x]) fa[x][0] = f; else { for(int i = 19;~i;i--) if(val[fa[f][i]] < val[x]) f = fa[f][i]; fa[x][0] = fa[f][0]; } s[x][0] = val[fa[x][0]]; for(int i = 1;i <= 19;i++) { fa[x][i] = fa[fa[x][i-1]][i-1]; if(!fa[x][i]) s[x][i] = inf; else s[x][i] = (s[fa[x][i-1]][i-1] + s[x][i-1]) >= inf?inf:(s[fa[x][i-1]][i-1]+s[x][i-1]); } } LL ask(LL x,LL tot) { if(tot-val[x] < 0) return 0; LL Ans = 1;tot -= val[x]; for(int i = 19;~i;i--) if(tot >= s[x][i]) tot -= s[x][i],x = fa[x][i],Ans = (Ans+(1<<i)); return Ans; } int main() { val[0] = inf; memset(s[1],0x3f,sizeof(s[1]));memset(s[0],0x3f,sizeof(s[0])); Q = read(); while(Q--) { int opt = read();LL R = read()^ans,W = read()^ans; if(opt == 1) { val[++si] = W; add(si,R); } else { ans = ask(R,W); printf("%lld\n",ans); } } }