树上查询

前言

好的，这是性质题，但是性质是典的，所以这是简单题，所以我唐。

max_{l \leq l^{'} \leq r^{'} \leq r \land r^{'} - l^{'} + 1 \geq k} {dep}_{LCA* (l^{'}, r^{'})}

性质：

这是出考场第一重击，后面都是平凡的：

${dep}_{LCA (l, r)} = {min}_{l}^{r - 1} {dep}_{LCA (a_{i}, a_{i + 1})}$

思路：

把 ${dep}_{LCA (a_{i}, a_{i + 1})}$ 记为 $b_{i}$ ，找出二元组 $(l_{i}, r_{i})$ ， $1 \leq l_{i} \leq i \leq r_{i} < n$ 使得 ${min}_{j = l_{i}}^{r_{i}} b_{j} = b_{i}$ ，且 $l e n = r_{i} - l_{i} + 1$ 最大。
题目转化为找到最大的 $b_{i}$ 满足 $| [l_{i}, r_{i} + 1] \cap [l, r] | \geq k$ 。
令 $l^{'} = l_{i}, r^{'} = r_{i} + 1$ 拆开式子：
- $l^{'} \leq l \leq r \leq r^{'}$ 时，要满足 $r - l + 1 \geq k$ 即 $l^{'} \leq l 且 r^{'} \geq r$ 。
- $l \leq l^{'} \leq r^{'} \leq r$ 时，要满足 $r^{'} - l^{'} + 1 \geq k$ 。
- $l^{'} \leq l \leq r^{'} \leq r$ 时，要满足 $r^{'} - l + 1 \geq k$ 即 $l^{'} \leq l 且 r^{'} \geq l + k - 1$ 。（这里默认 $r - l + 1 \geq k$ ，下同）
- $l \leq l^{'} \leq r \leq r^{'}$ 时，要满足 $r - l^{'} + 1 \geq k$ 即 $l^{'} \leq r - k + 1 且 r^{'} \geq r$ 。
这里发现第二种有点问题，其它的可以二维数点了。
我们不苛求算法一次处理所有情况，对 $k$ 从大到小做扫描线， $r^{'} - l^{'} + 1 \geq k$ 加入二元组。这时候不能变成三维数点（因为是双 $\log$ 的），想办法把二元组拍到序列上：你不是要 $l^{'} + k - 1 \leq r^{'}$ 且被 $(l, r)$ 包含吗，你把 $r^{'}$ 扔到序列上，查询区间 $[l + k - 1, r]$ ，这时候虽然 $l \leq l^{'}$ 是弱的，但是我们只要保证交集大于 $k$ 答案能取最大就行了，这点同 3、4。

总结

srds，真的是简单题，不过当时我连 T2 都挂了，我又有什么理由评判过去的自己呢。

代码

代码没怎么调，实现平凡，小样例和大样例一起过的。

cpp

#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define reg register
#define rep(i,a,b) for(reg int (i)=(a);(i)<=(b);++(i))
#define drep(i,a,b) for(reg int (i)=(a);(i)>=(b);--(i))
#define ll long long
#define il inline
#define pb push_back
#define ins insert
inline void cer_impl(){std::cerr<<'\n';}
template<typename T,typename... Args>
void cer_impl(T&& first, Args&&... rest){
    std::cerr<<std::forward<T>(first);
    if constexpr(sizeof...(rest)>0)
        std::cerr<<' ',cer_impl(std::forward<Args>(rest)...);
    else std::cerr<<'\n';
}
#define cer(...) cer_impl(__VA_ARGS__)
using namespace std;
const ll N=5e5+10,mod=1e9+7;
vector<int>e[N];
int fa[N],dep[N],hson[N],sz[N],top[N];
void pdfs1(int x,int f){
    dep[x]=dep[fa[x]=f]+1,sz[x]=1;
    for(auto to:e[x]){
        if(to==f)continue;
        pdfs1(to,x);
        sz[x]+=sz[to];
        if(sz[hson[x]]<sz[to])hson[x]=to;
    }
}
void pdfs2(int x,int t){
    top[x]=t;
    if(hson[x])pdfs2(hson[x],t);
    for(auto to:e[x]){
        if(top[to])continue;
        pdfs2(to,to);
    }
}
int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
        else y=fa[top[y]];
    }
    if(dep[x]<dep[y])return x;
    return y;
}
int b[N],l[N],r[N];
vector<pair<int,int>>node[N];
struct OP{
    int l,r,k,ans;
}q[N];
vector<pair<int,int>>qry[N];
struct BIT{
    int c[N];
    void add(int x,int v){
        for(;x<=500000;x+=(x&(-x)))c[x]=max(c[x],v);
    }
    int qry(int x){
        int res=0;
        for(;x;x-=(x&(-x)))res=max(res,c[x]);
        return res;
    }
}t;
int maxn[N<<2];
#define ls p<<1
#define rs p<<1|1
void bd(int p,int l,int r){
    if(l==r)return maxn[p]=dep[l],void();
    int mid=l+r>>1;bd(ls,l,mid);bd(rs,mid+1,r);
    maxn[p]=max(maxn[ls],maxn[rs]);
}
void cg(int p,int l,int r,int w,int v){
    maxn[p]=max(maxn[p],v);
    if(l==r)return ;
    int mid=l+r>>1;
    if(w<=mid)cg(ls,l,mid,w,v);
    else cg(rs,mid+1,r,w,v);
}
int query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return maxn[p];
    int res=0,mid=l+r>>1;
    if(L<=mid)res=query(ls,l,mid,L,R);
    if(mid<R)res=max(res,query(rs,mid+1,r,L,R));
    return res;
}
vector<int>p2q[N],p2c[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    rep(i,1,n-1){
        int u,v;cin>>u>>v;
        e[u].pb(v);e[v].pb(u);
    }
    pdfs1(1,0);pdfs2(1,1);
    rep(i,1,n-1)b[i]=dep[LCA(i,i+1)];
    rep(i,1,n-1){
        l[i]=i;while(b[l[i]-1]>=b[i])l[i]=l[l[i]-1];
    }
    drep(i,n-1,1){
        r[i]=i;while(b[r[i]+1]>=b[i])r[i]=r[r[i]+1];
    }
    rep(i,1,n-1){
        node[r[i]+1].pb({l[i],b[i]});
        p2c[r[i]+1-l[i]+1].pb(i);
    }
    int m;cin>>m;
    bd(1,1,n);
    rep(i,1,m){
        cin>>q[i].l>>q[i].r>>q[i].k;
        if(q[i].k==1){
            q[i].ans=query(1,1,n,q[i].l,q[i].r);
            continue;
        }
        p2q[q[i].k].pb(i);
        qry[q[i].r].pb({q[i].r-q[i].k+1,i});
        qry[q[i].r].pb({q[i].l,i});
        if(q[i].l+q[i].k-1<=n)
        qry[q[i].l+q[i].k-1].pb({q[i].l,i});
    }
    memset(maxn,0,sizeof maxn);
    int ans=0;
    drep(r,n,1){
        for(auto nd:node[r])t.add(nd.first,nd.second);
        for(auto it:qry[r])q[it.second].ans=max(q[it.second].ans,t.qry(it.first));
    }
    drep(k,n,1){
        for(auto it:p2c[k])cg(1,1,n,r[it]+1,b[it]);
        for(auto it:p2q[k])q[it].ans=max(q[it].ans,query(1,1,n,q[it].l+q[it].k-1,q[it].r));
    }
    rep(i,1,m)cout<<q[i].ans<<'\n';
    return 0;
}

树上查询https://blog.acerkaio.top/posts/2025/%E6%A0%91%E4%B8%8A%E6%9F%A5%E8%AF%A2

作者Shawn

发布于今日内

更新于今日内

许可协议 CC BY-NC-SA 4.0

署名-非商业性使用-相同方式共享 4.0 国际

题解扫描线

反馈与投诉

树上查询

前言 ​

树上查询 ​

性质： ​

思路： ​

总结 ​

代码 ​

前言

树上查询

性质：

思路：

总结

代码