题解：P11513 [ROIR 2017] 培训 (Day 2)

· · 题解

题解：P11513 [ROIR 2017] 培训 (Day 2)

类似于折跃点的，每个限制要求的点都在某棵子树的某一层，但这题更加简单。

65pts 做法

想找到所有限制的所有点，考虑到直接找不好找，我们 dfs 一遍记录所有点的 dfn 序以及所有子树的大小，每一层开一个 vector 记录这一层的点的 dfn 序。

我们想找到在某一层中找到属于某棵子树的点，利用 dfn 序就可以简单判断：对于子树 u，其子树的 dfn 序必定是连续的，且为 dfn_u\sim dfn_u+siz_u-1，那么当且仅当某一层的点的 dfn 序属于这个范围中时，该点便是在该层的属于子树 u 的节点。

统计答案时，观察到当 L 固定时，R 越大越能满足要求。因此采用双指针统计答案区间即可。

具体讲，在 dfs 的时候，记录点的 dfn 序和深度，以及每个 dfn 序对应的点的编号，再在每个深度开一个 vector 记录这一层所有点的 dfn 序。统计每个限制的时候，利用二分找到在某一层的 vector 中，这个限制要求的点的区间。遍历这个区间的每个节点，每个节点再开一个 vector，记录哪几个限制包含了该点。

在统计答案时，保持左端点不动，右端点右移，加入该点贡献，直到满足所有限制为止。记录答案后再将左端点右移，减去该点贡献即可。

code

所有注释均为调试信息。

100pts 做法

观察每个限制的区间不难发现，不存在哪两个区间是交叉的，即所有的区间都是以大区间包含小区间的方式存在。

那么我们就没有必要考虑所有的限制区间，只考虑被包含的小的区间，小的区间满足了，包含它的大的区间一定满足，只统计这个区间的答案即可。

#include<bits/stdc++.h>
#define ll long long
#define R1 register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R1 int x=0,t=1;R1 char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=2e5+10;
vector<int>g[N];
int id1[N],tot,id2[N],b[N];
void add(int ui,int vi)
{
    g[ui].push_back(vi);
    return;
}
void bfs(int st)
{
    queue<int>q;
    q.push(st);
    while(q.size()){
        int u=q.front();
        id1[u]=++tot;
        q.pop();
        for(int v:g[u]){
            q.push(v);
        }
    }
    tot=0;
    return;
}
vector<int>d[N],f[N];
int dep[N],siz[N],sum[N];
void dfs(int u,int fa)
{
    dep[u]=dep[fa]+1;
    siz[u]=1;
    id2[u]=++tot;
    b[tot]=u;
    d[dep[u]].push_back(id2[u]);
    for(int v:g[u]){
        dfs(v,u);
        siz[u]+=siz[v];
    }
    return;
}
struct node
{
    int l,r,k;
}q[N],q1[N];
bool cmp(node x,node y)
{
    if(x.k!=y.k) return x.k<y.k;
    if(x.l!=y.l) return x.l<y.l;
    return x.r<y.r;
}
signed main()
{
    int n=read();
    F(i,2,n){
        add(read(),i);
    }
    bfs(1);
    dfs(1,0);
    int m=read();
    F(i,1,m){
        int u=read(),k=read();
        k=dep[u]+k;
        int L=id2[u],R=id2[u]+siz[u]-1;
        int l=0,r=d[k].size()-1,ql=-1,qr=-1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(d[k][mid]<L){
                l=mid+1;
            }
            else r=mid-1,ql=mid;
        }
        l=0,r=d[k].size()-1;
        while(l<=r){
            int mid=l+r>>1;
            if(d[k][mid]>R) r=mid-1;
            else{
                l=mid+1;
                qr=mid;
            }
        }
        q[i].l=ql,q[i].r=qr,q[i].k=k;
    }
    sort(q+1,q+1+m,cmp);
    int tott=0;
    F(i,1,m){
        if(q[i].k!=q[i-1].k){
            q1[++tott]=q[i];
        }
        else{
            if(q[i].l!=q[i-1].l) q1[++tott]=q[i];
        }
    }
    m=tott;
    F(i,1,m){
        F(j,q1[i].l,q1[i].r){
            int tmp=b[d[q1[i].k][j]];
            f[tmp].push_back(i);
        }
    }

    int r=0,cnt=0;
    int minn=1e9,al,ar;
    for(int i = 1;i<=n;i++){
        while(r<n && cnt!=m){
            r++;
            for(int v:f[r]){
                if(sum[v]==0){
                    cnt++;
                }
                sum[v]++;
            }
        }
        if(cnt!=m){
            break;
        }
        int len=r-i+1;
        if(len<minn){
            minn=len;
            al=i,ar=r;
        }
        for(int v:f[i]){
            if(sum[v]==1){
                cnt--;
            }
            sum[v]--;
        }
    }
    cout << al << " " << ar << '\n';
    return 0;
}
/*

*/