P11364 [NOIP2024] 树上查询 题解

· · 题解

P11364 [NOIP2024] 树上查询 题解

题目大意

给你一颗树，有 q 个询问，每次给你一个区间和一个要求的长度，询问最深的区间 \operatorname{lca} 的深度。

题目分析

看到题目后大概能猜测出是一道数据结构题，当下的数据结构题目往往是需要找到性质才能更好地维护。

学过虚树的二次排序建树后可以迅速看出区间的 \operatorname{lca} 的深度转化为了 \min_{i=l}^{r-1}{\mathit{dep}_{\operatorname{lca}(i,i+1)}}。如果不知道虚树也可以手玩样例或讨论特殊情况来寻找性质。

在找到性质后，我们便自然地存下 \operatorname{lca}(i,i+1)。然后我们最后要求的答案就变成了 \max \min \mathit{dep}_{\operatorname{lca}(i,i+1)}。那么便考虑对于一个 \operatorname{lca}(i,i+1) 来说，它什么时候会变为某个区间的答案。

于是我们便可以对每一个 \operatorname{lca}(i,i+1) 求出它会成为的的最长区间 [L,R]，单调栈就可以解决。

那么如果该 \operatorname{lca}(i,i+1) 能对一个询问产生贡献，说明两个区间有交，可以写出式子：

&L\leq r-k+1\\ &R\ge l+k-1\\ &R-L+1\ge k\\ \end{aligned}

这很明显可以三维数点，用 cdq 分治便可以轻松解决。

Code

#include <bits/stdc++.h>
#define pb emplace_back
#define lowbit(x) (x&-x)
using namespace std;
namespace fasI{
    #define BF_SIZE 100000
    bool IOerr=0;
    inline char nc(){
        static char buf[BF_SIZE],*p1=buf+BF_SIZE,*pend=buf+BF_SIZE;
        if(p1==pend){
            p1=buf;
            pend=buf+fread(buf,1,BF_SIZE,stdin);
            if(pend==p1){IOerr=1;return -1;}
        }
        return *p1++;
    }
    inline bool bla(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void rd(int &x){
        char ch;
        while(bla(ch=nc()));
        if(IOerr){return;}
        for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
    }
    #undef BF_SIZE
};
using namespace fasI;
template<typename T>
inline void wr(T x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x<=9)
        putchar(x+48);
    else
        wr(x/10),putchar(x%10+48);
}
template<typename T>
inline void wrln(T x)
{
    wr(x),putchar('\n');
}
constexpr int N=1e6+5,inf=1e9;
int n,q;
vector<int>e[N];
int dep[N],son[N],siz[N],top[N],f[N][20],fa[N],lg2[N];
inline void dfs1(int u,int ft=0)
{
    fa[u]=ft;
    dep[u]=dep[ft]+1;
    siz[u]=1;
    for(auto v:e[u])
    {
        if(v==ft)
            continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v])
            son[u]=v;
    }
}
inline void dfs2(int u,int tp)
{
    top[u]=tp;
    if(son[u])
        dfs2(son[u],tp);
    for(auto v:e[u])
    {
        if(v==fa[u] || v==son[u])
            continue;
        dfs2(v,v);
    }
}
inline int \operatorname{lca}(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]>dep[v]?v:u;
}
inline void init()
{
    lg2[1]=0;
    for(int i=2;i<=n;i++)
        lg2[i]=lg2[i>>1]+1;
    for(int i=1;i<=n;i++)
        f[i][0]=dep[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<(j-1))<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int rmq(int l,int r)
{
    int t=lg2[r-l+1];
    return max(f[l][t],f[r-(1<<t)+1][t]);
}
int idx,cur,tot;
struct node{
    int id,L,R,len,dep,ans,pos;
    node(){id=L=R=len=dep=ans=pos=0;}
}s[N],s1[N];
inline bool cmp1(node x,node y)
{
    return x.len==y.len?x.pos<y.pos:x.len>y.len;
}
inline bool cmp2(node x,node y)
{
    return x.R==y.R?x.pos<y.pos:x.R>y.R;
}
int st[N],tp;
int ans[N];
struct BIT{
    int t[N];
    inline void add(int x,int val)
    {
        if(!val)
            return;
        while(x<=n)
            t[x]=max(t[x],val),x+=lowbit(x);
    }
    inline void del(int x)
    {
        while(x<=n)
            t[x]=0,x+=lowbit(x);
    }
    inline int ask(int x)
    {
        int res=0;
        while(x)
            res=max(res,t[x]),x-=lowbit(x);
        return res;
    }
}tr;
inline void cdq(int l,int r)
{
    if(l==r)
        return;
    int mid=l+r>>1,tot1=0;
    for(int i=l;i<=mid;++i)
        if(!s[i].pos)
            s1[++tot1]=s[i];
    for(int i=mid+1;i<=r;++i)
        if(s[i].pos)
            s1[++tot1]=s[i];
    sort(s1+1,s1+1+tot1,cmp2);
    for(int i=1;i<=tot1;i++)
        if(!s1[i].pos)
            tr.add(s1[i].L,s1[i].dep);
        else
            ans[s1[i].pos]=max(ans[s1[i].pos],tr.ask(s1[i].L));
    for(int i=1;i<=tot1;++i)
        if(!s1[i].pos)
            tr.del(s1[i].L);
    cdq(l,mid);
    cdq(mid+1,r);
}
int main()
{
    rd(n);
    for(register int i=1;i<n;++i)
    {
        int u,v;
        rd(u),rd(v);
        e[u].pb(v),e[v].pb(u);
    }
    dfs1(1);
    dfs2(1,1);
    init();
    for(register int i=1;i<n;++i)
    {
        node nw;
        nw.id=\operatorname{lca}(i,i+1);
        nw.dep=dep[nw.id];
        s[++idx]=(nw);
    }
    s[s[1].id].L=1;
    st[++tp]=1;
    for(register int i=2;i<n;++i)
    {
        int las=i;
        while(tp && s[st[tp]].dep>=s[i].dep)
            las=s[st[tp]].L,tp--;
        st[++tp]=i;
        s[i].L=las;
    }
    s[n-1].R=n-1;
    tp=0;
    st[++tp]=n-1;
    for(register int i=n-2;i>=1;--i)
    {
        int las=i;
        while(tp && s[st[tp]].dep>=s[i].dep)
            las=s[st[tp]].R,tp--;
        st[++tp]=i;
        s[i].R=las;
    }
    for(register int i=1;i<=idx;++i)
        s[i].R++,s[i].len=s[i].R-s[i].L+1;
    rd(q);
    for(register int i=1;i<=q;++i)
    {
        int l,r,k;
        rd(l),rd(r),rd(k);
        if(k!=1)
        {
            idx++;
            s[idx].id=0;
            s[idx].L=r-k+1;
            s[idx].R=l+k-1;
            s[idx].len=k;
            s[idx].dep=0;
            s[idx].ans=0;
            s[idx].pos=i;
        }
        else
            ans[i]=(l==r)?dep[l]:rmq(l,r);
    }
    sort(s+1,s+1+idx,cmp1);
    cdq(1,idx);
    for(register int i=1;i<=q;++i)
        wrln(ans[i]);
    return 0;
}

Tips

别忘记 k=1 的时候要特判。