题解归档 - cf932D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf932D
• 本地来源：problems/cf932D/idea.md
• 题目链接：https://codeforces.com/contest/932/problem/D
• 原始标题：cf932D Tree

思路

cf932D Tree

题意

动态向以 1 为根的树加叶子（带权），支持查询：从节点 R 出发沿祖先方向走，相邻两点 i→j（i 是 j 祖先）需满足 w[i]≥w[j] 且路径上无 k 使 w[k]≥w[j]；权值和 ≤ X 时最长链长。查询带 XOR 混淆（last 为上次 type2 答案）。

思路

树上倍增（权值单调祖先跳）：

• fa[v][0]：从 v 向上第一个「可接在 v 后面」的祖先 u（即 w[u]≥w[v]，且 v→u 路径上无权 ≥w[v]）。
• 加边 pa→v：若 w[pa]≥w[v] 则 fa[v][0]=pa；否则从 pa 倍增找最远满足 w[·]<w[v] 的节点，再取其 fa[·][0]。
• sum[v][i]：沿 fa[v][i] 跳 2^i 步所经节点权值和（不含 v 自身）。
• 查询：先扣 w[R]，再从高到低倍增，能跳则 ans += 2^i。

复杂度

预处理每点 O(log N)，查询 O(log N)，总 O(Q log N)。

验证

样例 4 组 + stress.py 对拍 brute.cpp（q≤12，权值≤4）。

代码

来源：problems/cf932D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:24:21
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
const ll maxn=400005;
ll fa[maxn][22],sum[maxn][22],w[maxn],cnt,last,q,i,j,k,zc,pd,cur,dq,ans;
void adde(ll pa,ll va){
    cnt++;
    w[cnt]=va;
    if(w[pa]>=va) fa[cnt][0]=pa;
    else{
        cur=pa;
        for(i=20;i>=0;i--){
            if(fa[cur][i] and w[fa[cur][i]]<va) cur=fa[cur][i];
        }
        if(fa[cur][0] and w[fa[cur][0]]>=va) fa[cnt][0]=fa[cur][0];
        else fa[cnt][0]=0;
    }
    if(!fa[cnt][0]) sum[cnt][0]=inf;
    else sum[cnt][0]=w[fa[cnt][0]];
    for(i=1;i<=20;i++){
        fa[cnt][i]=fa[fa[cnt][i-1]][i-1];
        if(fa[cnt][i]) sum[cnt][i]=sum[cnt][i-1]+sum[fa[cnt][i-1]][i-1];
        else sum[cnt][i]=inf;
    }
}
ll query(ll r,ll x){
    if(w[r]>x) return 0;
    x-=w[r];
    cur=r;
    ans=1;
    for(i=20;i>=0;i--){
        if(fa[cur][i] and sum[cur][i]<=x){
            x-=sum[cur][i];
            cur=fa[cur][i];
            ans+=(1ll<<i);
        }
    }
    return ans;
}
int main(){
    scanf("%lld",&q);
    cnt=1;
    w[1]=0;
    last=0;
    while(q--){
        ll opr,a,b;
        scanf("%lld%lld%lld",&opr,&a,&b);
        a^=last;
        b^=last;
        if(opr==1){
            adde(a,b);
        }else{
            last=query(a,b);
            printf("%lld\n",last);
        }
    }
    return 0;
}