Luogu

LOJ

分析

首先有一个结论：最终状态一定满足所有边都连向 $n$ 。那么步数就等于初始状态下不与 $n$ 相连的边数。

把所有初始与 $n$ 相连的边按另一个端点排序。那么对于排序后相邻的两个点 $l,r(l+1\neq r)$ ，一定会存在一条边 $(l,r)$ 。那么图中一定会存在一个点 $mid$ ，使得初始状态下存在两条边 $(l,mid)$ 和 $(mid,r)$ 。那么我们旋转一次后就可以得到 $(mid,n)$ 。然后整个区间 $[l,r]$ 会变成两个区间 $[l,mid]$ 和 $[mid,r]$ 。

可以发现这构成了一棵二叉树。那么把所有 $l,r$ 拿出来就构成了一片二叉树森林。

考虑方案数如何计算。显然每个节点只有在其父亲被操作后才能操作，那么每个节点的贡献为 $\large\frac{(sz[ls]+sz[rs])!}{sz[ls]!sz[rs]!}$ ，直接乘到一起就是方案数了。

考虑修改怎么做。第一种情况是旋转了一条边 $(i,n)$ ，此时相当于删去了一棵二叉树的根节点，那么最优步数会减 $1$ ；第二种情况是旋转了一条端点不为 $n$ 的边，此时相当于 rotate 了一棵子树（类似 Splay 中的 rotate），显然最优步数是不变的。

修改后的方案数相当于除去以前的贡献再乘上现在的贡献，画个图就可以推出来了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <map>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=1e9+7;

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int W,n,m;
int fac[N],ifac[N];
vector<int> E[N];
int fa[N],ls[N],rs[N],sz[N];
int tot=0,sum=0,ans=1;
map<pair<int,int>,int> M;

inline int calc(int n,int m) {
    return 1ll*fac[n+m]*ifac[n]%mod*ifac[m]%mod;
}
inline int calcinv(int n,int m) {
    return 1ll*ifac[n+m]*fac[n]%mod*fac[m]%mod;
}

inline void addEdge(int u,int v) {
    E[u].push_back(v),E[v].push_back(u);
}

inline void dfs(int& x,int l,int r,int f) {
    if (l+1==r) return;
    x=++tot,M[make_pair(l,r)]=x,fa[x]=f;
    int mid=*(--lower_bound(E[l].begin(),E[l].end(),r));
    dfs(ls[x],l,mid,x),dfs(rs[x],mid,r,x);
    sz[x]=sz[ls[x]]+sz[rs[x]]+1;
    ans=1ll*ans*calc(sz[ls[x]],sz[rs[x]])%mod;
}

int main() {
    fac[0]=1;
    for (re int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[N-1]=qpow(fac[N-1],mod-2);
    for (re int i=N-1;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;

    W=read(),n=read();
    for (re int i=1;i<n;++i) addEdge(i,i+1);
    addEdge(n,1);
    for (re int i=1;i<=n-3;++i) {
        int u=read(),v=read();
        addEdge(u,v);
    }
    for (re int i=1;i<=n;++i) sort(E[i].begin(),E[i].end());

    for (re int i=0;i<E[n].size()-1;++i) {
        int x=0; dfs(x,E[n][i],E[n][i+1],0);
        ans=1ll*ans*calc(sum,sz[x])%mod,sum+=sz[x];
    }

    if (W) printf("%d %d\n",sum,ans);
    else printf("%d\n",sum);

    m=read();
    while (m--) {
        int a=read(),b=read(),x=M[make_pair(a,b)];
        if (fa[x]) {
            int f=fa[x],now=ans;
            now=1ll*now*calcinv(sz[ls[x]],sz[rs[x]])%mod;
            now=1ll*now*calcinv(sz[ls[f]],sz[rs[f]])%mod;
            now=1ll*now*calc(sz[rs[x]],sz[rs[f]])%mod;
            now=1ll*now*calc(sz[ls[x]],sz[rs[x]]+sz[rs[f]]+1)%mod;
            if (W) printf("%d %d\n",sum,now);
            else printf("%d\n",sum);
        } else {
            int now=ans;
            now=1ll*now*calcinv(sz[ls[x]],sz[rs[x]])%mod;
            now=1ll*now*calcinv(sum-sz[x],sz[x])%mod;
            now=1ll*now*calc(sum-sz[x],sz[ls[x]])%mod;
            now=1ll*now*calc(sum-sz[x]+sz[ls[x]],sz[rs[x]])%mod;
            if (W) printf("%d %d\n",sum-1,now);
            else printf("%d\n",sum-1);
        }
    }

    return 0;
}