题解 | #树和序列#

分析：给一棵树添加点，查询一个点固定性质下的权值和约束的路径。

这里的固定性质指，该性质导致的路径总是不改变的，可以记录好后不发生改变；

这里的权值和约束，指的是类似前缀和性质下的，和有上限的约束。

方法：由于性质固定，按照查询需求，因此保留符合性质的点进行重新建树；

由于约束是权值和的，因此只需要维护一个类似前缀和的数组。

算法：重新建树时，找一个权值恰好大于等于当前点的作为第一个父亲，可以利用向上倍增；同时维护一个倍增的前缀和数组，表示从第 到 个祖先的权值和。

if 1:
    inf = float('inf')
    import sys
    input = lambda: sys.stdin.readline().strip()
    I = lambda: input()
    II = lambda: int(input())
    IS = lambda: input().split()
    MII = lambda: map(int, input().split())
    LMII = lambda: list(map(int, input().split()))
    L01 = lambda: list(int(x) for x in input())
    LMZ = lambda A: list(map(list, zip(*A)))
    from collections import deque,defaultdict,Counter

maxQ = 4 * 10 ** 5 + 5

def Solve():
    fa = [[0] * 31 for i in range(maxQ)]
    dp = [[0] * 31 for i in range(maxQ)] # 从第 1 个到 2 ^ j 个祖先的权值和
    val = [0] * (maxQ)

    def add_edge(u, v, w):
        nonlocal val,fa,dp
        val[v] = w

        if val[u] >= val[v]:
            fa[v][0] = u
            dp[v][0] = val[u]
        else:
            for j in range(30, -1, -1):
                if fa[u][j] != 0 and val[fa[u][j]] < val[v]:
                    u = fa[u][j]
            u = fa[u][0]
            fa[v][0] = u
            dp[v][0] = val[u]
    
    def cal(v):
        nonlocal dp,fa
        for j in range(1, 31):
            if fa[v][j - 1] != 0:
                dp[v][j] = dp[v][j - 1] + dp[fa[v][j - 1]][j - 1]
                fa[v][j] = fa[fa[v][j - 1]][j - 1]
    
    def query(u, w):
        res = 0
        if val[u] <= w:
            res += 1
            w -= val[u]
            for j in range(30, -1, -1):
                if fa[u][j] != 0 and w - dp[u][j] >= 0:
                    w -= dp[u][j]
                    res += 2 ** j
                    u = fa[u][j]
        return res

    Q = II()
    cnt = 1
    last = 0
    for _ in range(Q):
        op,p,q = MII()
        p ^= last
        q ^= last
        if op == 1:
            cnt += 1
            add_edge(p, cnt, q)
            cal(cnt)
        elif op == 2:
            last = query(p, q)
            print(last)
    
    
if __name__ == '__main__':
    T = 1
    # T = int(input())
    for i in range(T):
        Solve()