P11666 题解

· · 题解

Problem Link

题目大意

给定 n 个点的基环内向树森林，m 条个棋子要从 u\to v，每个时刻可以把每个棋子移动到父亲，但同一个格子的棋子只能移动一个，求所有棋子到达的最小时间。

数据范围：n,m\le 2\times 10^5。

思路分析

首先我们每轮肯定有限移动距离远终点的点，这样可以得到一个朴素暴力。

但是这个做法无法优化，需要更好地刻画答案，考虑每条边对答案的贡献，即对于每条边 u\to fa_u，我们计算所有棋子都离开 u 的最小时刻 w_u。

设所有经过这条边的棋子到 u 的距离为 d_1\sim d_k（按离开顺序排列），考虑每个棋子离开这条边的时刻 t_i，那么有 t_i\ge \max(d_i,t_{i-1})+1。

此时 w_u=\max d_{k-i+1}+i，显然 d 升序时取到最小。

我们能证明答案恰好能取到下界 \max w_u，观察 w_u 的计算，相当于对于一些在 u 的前驱处重合的棋子，我们钦定他们可以一起运动到 u 再考虑重合的问题。

直观上来看这个做法是很对的，因为重合后这两个棋子已经没有本质区别，无论谁先到 u 都是等价的。

即所有经过这条边的棋子的贡献可以正确计算，但有一些不经过 u 的棋子，我们还要考虑他对答案的影响。

对于一条链 x\to y\to u，如果有一个棋子从 x\to y，那么他在 x 处可能卡住其他到 u 的径棋子

根据我们的朴素贪心，这显然是不可能的，因为经过 u 的棋子剩余距离更大，因此 x\to y 的棋子一定会在这些棋子离开 x 之后再运动，所有这些棋子无影响。

所以我们能证明最优解中，最后一个棋子离开这条边的时刻恰好就是 w_u。

那么考虑树的情况，把过 u 的路径用线段树合并，维护每条路径终点的深度，push up 时左边的最大答案加上右边的终点个数，这样就能维护 w_u 了。

然后处理基环树，我们只要让覆盖每条边的棋子集合正确即可。

随便找一条边破环为链，然后把整棵基环树复制一遍接到末尾，如果过 x\to y 路径过环边 p\to fa_{p}，就拆成 x\to p 和 x'\to y，容易证明此时覆盖每条路径的棋子集合不变。

时间复杂度 \mathcal O((n+m)\log n)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
struct SegmentTree {
    int tot,ls[MAXN*20],rs[MAXN*20],mx[MAXN*20],ct[MAXN*20];
    void psu(int p) {
        ct[p]=ct[ls[p]]+ct[rs[p]],mx[p]=max(mx[ls[p]]+ct[rs[p]],mx[rs[p]]);
    }
    void ins(int u,int op,int l,int r,int &p) {
        if(!p) p=++tot;
        if(l==r) return ct[p]+=op,mx[p]=(ct[p]?l+ct[p]:0),void();
        int mid=(l+r)>>1;
        u<=mid?ins(u,op,l,mid,ls[p]):ins(u,op,mid+1,r,rs[p]);
        psu(p);
    }
    void merge(int l,int r,int q,int &p) {
        if(!q||!p) return p|=q,void();
        if(l==r) return ct[p]+=ct[q],mx[p]=(ct[p]?l+ct[p]:0),void();
        int mid=(l+r)>>1;
        merge(l,mid,ls[q],ls[p]),merge(mid+1,r,rs[q],rs[p]);
        psu(p);
    }
}   T;
vector <int> G[MAXN],D[MAXN];
int n,m,fa[MAXN],dsu[MAXN],tp[MAXN];
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
int dcnt,dfn[MAXN],rdn[MAXN],dep[MAXN];
void dfs1(int u) {
    dfn[u]=++dcnt;
    for(int v:G[u]) dep[v]=dep[u]+1,tp[v]=u?tp[u]:v,dfs1(v);
    rdn[u]=dcnt;
}
int op[MAXN],ans,rt[MAXN];
void ins(int x,int y) { ++op[y],D[x].push_back(dep[y]); }
void dfs2(int u) {
    for(int v:G[u]) dfs2(v),T.merge(0,2*n,rt[v],rt[u]);
    T.ins(dep[u],op[u],0,2*n,rt[u]);
    for(int i:D[u]) T.ins(i,-1,0,2*n,rt[u]);
    ans=max(ans,T.mx[rt[u]]-dep[u]);
}
signed main() {
    scanf("%d",&n),iota(dsu+1,dsu+n+1,1);
    for(int i=1;i<=n;++i) scanf("%d",&fa[i]),fa[i+n]=fa[i]+n,dsu[find(i)]=find(fa[i]);
    for(int i=1;i<=n;++i) if(dsu[i]==i) {
        int x=i;
        for(;dsu[x];x=fa[x]) dsu[x]=0;
        fa[x+n]=fa[x],fa[x]=0;
    }
    for(int i=1;i<=2*n;++i) G[fa[i]].push_back(i);
    dfs1(0),scanf("%d",&m);
    for(int x,y;m--;) {
        scanf("%d%d",&x,&y);
        if(dfn[y]<=dfn[x]&&dfn[x]<=rdn[y]) ins(y,x);
        else if(dfn[y]<=dfn[x+n]&&dfn[x+n]<=rdn[y]) ins(y,x+n),ins(tp[y],x);
        else return puts("-1"),0;
    }
    dfs2(0),printf("%d\n",ans);
    return 0;
}