P1056 · OFFICIAL SOLUTION

P1056 树上查询官方题解

Gioush OJ · P1056 树上查询

【数据点 1∼21\sim 21∼2】

这一档保证 $n,q\leq300$ 。预处理任意连续区间的权值和与最近公共祖先深度。
对每次查询枚举 $l\leq a\leq b\leq r$ ，检查区间权值和是否达到 $k$ ，并更新最大深度。
时间复杂度为 $\mathcal{O}(n^2+qn^2)$ ，空间复杂度为 $\mathcal{O}(n^2)$ 。

【数据点 3∼53\sim 53∼5】

考虑二分答案深度 $d$ 。深度至少为 $d$ 的最近公共祖先，说明整个区间位于某个深度为 $d$ 的结点子树中。
枚举深度为 $d$ 的结点，计算它的子树编号区间与 $[l,r]$ 的交集权值和，判断是否至少为 $k$ 。
一次判定需要 $\mathcal{O}(n)$ ，每次查询需要 $\mathcal{O}(n\log n)$ ，足以通过 $n,q\leq2\times10^3$ 。

【数据点 6∼96\sim 96∼9】

这一档的树是一条链，所以结点 $i$ 的深度就是 $i$ ，区间 $[a,b]$ 的最近公共祖先就是结点 $a$ 。
对一次查询，固定左端点 $a$ 后，最大的可用权值和为 $w(a,r)$ 。我们需要找到满足 $w(a,r)\geq k$ 的最大 $a$ 。
权值均为正，前缀和严格递增，可以二分这个位置。每次查询时间复杂度为 $\mathcal{O}(\log n)$ 。

【数据点 10∼1310\sim 1310∼13】

这一档保证 $k=w(l,r)$ 。由于权值均为正，只有完整区间 $[l,r]$ 的权值和能够达到 $k$ 。
因而答案就是结点 $l,l+1,\ldots,r$ 的最近公共祖先深度。
在深度优先遍历编号下，这个最近公共祖先等于 $\operatorname{lca}(l,r)$ ，使用倍增即可回答。

【数据点 14∼2014\sim 2014∼20】

这一档保证 $k\leq\min_{i=l}^{r}w_i$ ，所以任意单点区间都满足权值条件。
单点区间 $[i,i]$ 的最近公共祖先就是结点 $i$ 。答案转化为 $[l,r]$ 中结点深度的最大值。
对深度数组建立稀疏表或线段树即可。预处理 $\mathcal{O}(n\log n)$ ，每次查询 $\mathcal{O}(1)$ 或 $\mathcal{O}(\log n)$ 。

【正解】

固定深度 $d$ ，考虑深度为 $d$ 的一个结点 $u$ ，其子树编号区间记为 $I_u$ 。

若一个合法区间的最近公共祖先深度至少为 $d$ ，那么该区间一定完整位于某个 $I_u$ 中。
反过来， $I_u\cap[l,r]$ 仍然是连续区间。若这个交集的权值和至少为 $k$ ，直接选择其中一段达到 $k$ 的前缀即可。
因此深度 $d$ 可行，当且仅当存在一个深度为 $d$ 的结点，使其子树与询问区间的交集权值和至少为 $k$ 。

【数据结构实现】

同一深度的子树区间互不相交，并且按照左端点与右端点同时递增的顺序排列。
与 $[l,r]$ 相交的子树构成一个连续段。第一棵与最后一棵子树可能只被截取一部分，中间子树一定完整包含在 $[l,r]$ 中。
使用权值前缀和计算两个边界交集。对每个深度的完整子树权值建立稀疏表，中间部分直接查询最大值。
两次二分找到相交子树段，一次判定的时间复杂度为 $\mathcal{O}(\log n)$ 。

【实现与复杂度】

若深度 $d$ 可行，那么所有小于 $d$ 的深度也可行。因此可以二分最大的可行深度。
预处理所有子树右端点、结点深度、权值前缀和，以及每个深度的稀疏表。
预处理时间与空间复杂度为 $\mathcal{O}(n\log n)$ ，每次查询时间复杂度为 $\mathcal{O}(\log^2 n)$ 。
权值前缀和、子树权值与询问阈值需要使用 long long。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/24Name:query.cpp5You steal,I kill.6*/7#include <cstdio>8#include <vector>9#include <algorithm>10#define MAXN 20001011using namespace std;12int c,T,n,q,MaxDepth,LastDepth,Father[MAXN],Depth[MAXN],Right[MAXN];13long long Line[MAXN],Pre[MAXN];14struct Data {15    vector <int> St,Ed,Log;16    vector <long long> Sum;17    vector <vector <long long> > ST;18    void Clear(){St.clear();Ed.clear();Log.clear();Sum.clear();ST.clear();}19    void Build(){20        int Len=St.size();21        Sum.resize(Len);Log.assign(Len+1,0);22        for(int i=0;i<Len;i++) Sum[i]=Pre[Ed[i]]-Pre[St[i]-1];23        for(int i=2;i<=Len;i++) Log[i]=Log[i>>1]+1;24        if(!Len) return;25        ST.assign(Log[Len]+1,vector <long long>(Len));ST[0]=Sum;26        for(int j=1;j<(int)ST.size();j++){27            for(int i=0;i+(1<<j)<=Len;i++){28                ST[j][i]=max(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);29            }30        }31        return;32    }33    long long Query(int l,int r){34        if(l>r) return -1;35        int p=Log[r-l+1];36        return max(ST[p][l],ST[p][r-(1<<p)+1]);37    }38}Level[MAXN];39bool Check(int d,int l,int r,long long k){40    Data &Now=Level[d];41    int x=lower_bound(Now.Ed.begin(),Now.Ed.end(),l)-Now.Ed.begin();42    int y=upper_bound(Now.St.begin(),Now.St.end(),r)-Now.St.begin()-1;43    if(x>y) return false;44    int Left=max(l,Now.St[x]),RightPos=min(r,Now.Ed[x]);45    long long Ret=Left<=RightPos?Pre[RightPos]-Pre[Left-1]:0;46    if(x!=y){47        Left=max(l,Now.St[y]);RightPos=min(r,Now.Ed[y]);48        if(Left<=RightPos) Ret=max(Ret,Pre[RightPos]-Pre[Left-1]);49    }50    Ret=max(Ret,Now.Query(x+1,y-1));51    return Ret>=k;52}53int Calc(int l,int r,long long k){54    int Left=1,RightPos=MaxDepth;55    while(Left<RightPos){56        int Mid=(Left+RightPos+1)>>1;57        if(Check(Mid,l,r,k)) Left=Mid;58        else RightPos=Mid-1;59    }60    return Left;61}62void Solve(){63    for(int i=1;i<=LastDepth;i++) Level[i].Clear();64    scanf("%d%d",&n,&q);65    Father[1]=0;Depth[1]=1;MaxDepth=1;66    for(int i=2;i<=n;i++) scanf("%d",&Father[i]);67    Pre[0]=0;68    for(int i=1;i<=n;i++){69        scanf("%lld",&Line[i]);70        Pre[i]=Pre[i-1]+Line[i];71        Right[i]=i;72        if(i>1) Depth[i]=Depth[Father[i]]+1;73        MaxDepth=max(MaxDepth,Depth[i]);74    }75    for(int i=n;i>=2;i--) Right[Father[i]]=max(Right[Father[i]],Right[i]);76    for(int i=1;i<=n;i++){77        Level[Depth[i]].St.push_back(i);78        Level[Depth[i]].Ed.push_back(Right[i]);79    }80    for(int i=1;i<=MaxDepth;i++) Level[i].Build();81    LastDepth=MaxDepth;82    while(q-->0){83        int l,r;long long k;84        scanf("%d%d%lld",&l,&r,&k);85        printf("%d\n",Calc(l,r,k));86    }87    return;88}89int main(){90    scanf("%d%d",&c,&T);91    while(T-->0) Solve();92    return 0;93}