Loading... [Codeforce 932 D](https://codeforces.com/contest/932/problem/D) 求往祖先走不超过$sum$的距离所经历的点的最多个数,并且只能走向权值大于自身的点。 每次添加点的时候倍增的往上跳,找到满足条件的最近的点,因为之前保存的父节点一定是权值递增的,所以可以一直往上跳。 查询的时候倍增查询即可。 ```cpp #include<bits/stdc++.h> typedef long long ll; using namespace std; const int N = 4e5 + 10; const int up = 20; const ll inf = 1e18; int tot,m; ll last,p,q; ll w[N], s[N][25]; int fat[N][25]; void add(int p, int q) { w[++tot] = q; if (w[tot] <= w[p]){ fat[tot][0] = p; } else{ for (int j = up; j >= 0; j--) { if (w[fat[p][j]] < w[tot]) p= fat[p][j]; } fat[tot][0] = fat[p][0]; } if (fat[tot][0] == 0){ s[tot][0] = inf; } else{ s[tot][0] = w[fat[tot][0]]; } for (int j = 1; j <= 20; j++) { fat[tot][j] = fat[fat[tot][j - 1]][j - 1]; s[tot][j] = fat[tot][j] == 0 ? inf : s[tot][j - 1] + s[fat[tot][j - 1]][j - 1]; } } ll query(int v, ll sum) { ll ans = 0; if (sum >= w[v]) { sum -= w[v]; ans++; for (int j = 20; j >= 0; j--) { if (s[v][j] <= sum){//没走到就一直往上走 ans += (1 << j); sum -= s[v][j]; v = fat[v][j]; } } } return ans; } int main() { w[0] = inf; tot = 1; scanf("%d", &m); memset(s[1], 0x7f, sizeof(s[1])); while (m--) { int op; scanf("%d%lld%lld", &op, &p, &q); p ^= last,q ^= last; if (op==1) add(p, q); else printf("%d\n", last = query(p, q)); } return 0; } ``` Last modification:November 14th, 2019 at 05:34 pm © 允许规范转载 Support 如果觉得我的文章对你有用,请随意赞赏 ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat