题解：P14380 【MX-S9-T3】「LAOI-16」天外来物

yiyang77 · 2026-11-11 08:31:46 · 题解

题目要求不同的 f(l,r)，所以我们要对这种点集进行去重。我们定义一的 f(l,r) 是极小区间当且仅当它不是 f(l+1,r) 或 f(l,r-1)，这样我们就可以不重不漏的计数。

考虑这样的极小区间满足什么性质。可以发现，l 和 r 都是点集的叶子，因为考虑如他们下面还挂了点，若这个点 \notin[l,r]，那么没有必要加这个点；若这个点 \in[l,r]，那么在计算更小区间时已经计算过这个点集。

所以，我们用 pre_i 表示以 i 为右端点，可以成为极小区间的最小的 l，suf_i 表示以 i 为左端点，可以成为极小区间的最大的 r。考虑如何算 pre 和 suf。pre_i 是 i 的孩子的子树和除去 i 的子树的剩余树中出现的次大值 +1，因为 i 必须为叶子，若取到次大值，那么我们也必须去最大值的树，那么就去了 i 的两棵子树，i 不会成为叶子。suf_i 同理，是它的子树中次小值 -1。

现在，一个 [l,r] 是极小区间当且仅当 pre_r\le l 且 suf_l\ge r。这样我们可以将询问离线。在 suf_i+1 删除 i，然后对于 [pre_i,i] 区间加一。[l,i] 的答案为 [l,i] 中还没不删的节点加上它被覆盖的次数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+7;
int n,q,dfn[N],sz[N],tot,pre[N],suf[N];ll ans[N];
vector<pair<int,int>> Q[N];
vector<int> G[N],son[N],del[N];
inline void dfs(int u,int fa){
    dfn[u]=++tot,sz[u]=1;
    for(int &v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
        sz[u]+=sz[v],son[u].emplace_back(v);
    }
}
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
struct seg_min{
    int tr[N<<2];
    seg_min(){memset(tr,0x3f,sizeof(tr));}
    inline void pushup(int rt){tr[rt]=min(tr[ls],tr[rs]);}
    inline void add(int rt,int l,int r,int p,int val){
        if(l==r){tr[rt]=val;return ;}
        if(p<=mid)add(lson,p,val);
        else add(rson,p,val);
        pushup(rt);
    }
    inline int ask(int rt,int l,int r,int L,int R){
        if(L>R)return 2e9;
        if(L<=l&&r<=R)return tr[rt];
        if(R<=mid)return ask(lson,L,R);
        else if(L>mid)return ask(rson,L,R);
        else return min(ask(lson,L,R),ask(rson,L,R));
    }
} trmin;
struct seg_max{
    int tr[N<<2];
    inline void pushup(int rt){tr[rt]=max(tr[ls],tr[rs]);}
    inline void add(int rt,int l,int r,int p,int val){
        if(l==r){tr[rt]=val;return ;}
        if(p<=mid)add(lson,p,val);
        else add(rson,p,val);
        pushup(rt);
    }
    inline int ask(int rt,int l,int r,int L,int R){
        if(L>R)return 0;
        if(L<=l&&r<=R)return tr[rt];
        if(R<=mid)return ask(lson,L,R);
        else if(L>mid)return ask(rson,L,R);
        else return max(ask(lson,L,R),ask(rson,L,R));
    }
} trmax;
struct seg_ask{
    struct node{int num;ll cnt,tag;}tr[N<<4];
    inline void update(int rt,ll val){tr[rt].cnt+=1ll*tr[rt].num*val,tr[rt].tag+=val;}
    inline void pushdown(int rt){
        if(!tr[rt].tag)return ;
        update(ls,tr[rt].tag),update(rs,tr[rt].tag);
        tr[rt].tag=0;
    }
    inline void pushup(int rt){tr[rt].num=tr[ls].num+tr[rs].num,tr[rt].cnt=tr[ls].cnt+tr[rs].cnt;}
    inline void change(int rt,int l,int r,int p,int val){
        if(l==r){tr[rt].num=val;return ;}
        pushdown(rt);
        if(p<=mid)change(lson,p,val);
        else change(rson,p,val);
        pushup(rt);
    }
    inline void add(int rt,int l,int r,int L,int R){
        if(L<=l&&r<=R){update(rt,1);return ;}
        pushdown(rt);
        if(L<=mid)add(lson,L,R);
        if(R>mid)add(rson,L,R);
        pushup(rt);
    }
    inline ll ask(int rt,int l,int r,int L,int R){
        if(L<=l&&r<=R)return tr[rt].cnt;
        pushdown(rt);
        if(R<=mid)return ask(lson,L,R);
        else if(L>mid)return ask(rson,L,R);
        else return ask(lson,L,R)+ask(rson,L,R);
    }
} trask;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v,G[u].emplace_back(v),G[v].emplace_back(u);
    }dfs(1,0);
    for(int i=1,maxn,sec,val;i<=n;++i){
        trmax.add(1,1,n,dfn[i],i);
        maxn=0,sec=0;
        for(int &v:son[i]){
            val=trmax.ask(1,1,n,dfn[v],dfn[v]+sz[v]-1);
            if(val>maxn)sec=maxn,maxn=val;
            else if(val>=sec)sec=val;
        }
        val=max(trmax.ask(1,1,n,1,dfn[i]-1),trmax.ask(1,1,n,dfn[i]+sz[i],n));
        if(val>=maxn)sec=maxn,maxn=val;
        else if(val>=sec)sec=val;
        pre[i]=sec+1;
    }
    for(int i=n,minn,sec,val;i>=1;--i){
        trmin.add(1,1,n,dfn[i],i);
        minn=n+1,sec=n+1;
        for(int &v:son[i]){
            val=trmin.ask(1,1,n,dfn[v],dfn[v]+sz[v]-1);
            if(val<minn)sec=minn,minn=val;
            else if(val<sec)sec=val;
        }
        val=min(trmin.ask(1,1,n,1,dfn[i]-1),trmin.ask(1,1,n,dfn[i]+sz[i],n));
        if(val<minn)sec=minn,minn=val;
        else if(val<sec)sec=val;
        suf[i]=sec-1;del[sec].emplace_back(i);
    }
    for(int i=1,l,r;i<=q;i++) cin>>l>>r,Q[r].emplace_back(l,i);
    for(int i=1;i<=n;i++){
        for(int &l:del[i])trask.change(1,1,n,l,0);
        trask.change(1,1,n,i,1);trask.add(1,1,n,pre[i],i);
        for(pair<int,int> &j:Q[i]) ans[j.second]=trask.ask(1,1,n,j.first,i);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
    return 0;
}