传送门

这是什么神仙操作...

首先要注意一些性质.首先每一个\((x,n)\)的边可以把当前多边形分成两半,这两半的操作是独立的.然后对于某一个没有\((x,n)\)的边的多边形,最优操作是唯一的.拿样例举例,必须先选\((1,5)\),然后多边形被分成两半,这两半分别只能选\((1,3)\),\((3,5)\).

可以发现,这里每次操作的多边形上的点分别是\(l,l+1...,r(l\ge 1,r<n,r-l>1)\)和\(n\),然后最优方案要选\((l,r)\)这条边,把多边形分成\(\{[l,mid],n\}\)和\(\{[mid,r],n\}\)(\(mid\)是当前多边形中的\(l\)和\(r\)除了\(n\)以外的那个公共点)两部分.根据这个我们可以建出若干二叉树,每个点的左右两个儿子是这个多边形操作之后的左右两半多边形(不能是三角形,因为三角形不用操作)

考虑计算答案,第一问答案为这些二叉树节点个数(也就是\(n-1-\)\((x,n)\)边条数),因为每个节点都是一次操作;第二问答案,因为这个二叉树每个节点要在他的父亲之后才能操作,所以如果把每个点看成一个排列中的数,就是要求满足\(x\)在\(fa_x\)后面的排列个数,这个直接把SAO蒯过来就好了对于每个节点的子树,首先这个点要放在第一位,两个儿子子树的序列之间是没有先后关系的,所以一个节点对答案的贡献是\(\binom{sz_{ch_{x,0}}+sz_{ch_{x,1}}}{sz_{ch_{x,0}}}\),把这些贡献乘起来就好了.然后对于所有二叉树的根,我们把他们向一个超级根连边,因为相互没有影响,所以答案还要乘上把所有树合并的方案,类似于树型背包,每次把一个并到总集合,然后类似于上面的组合数即可

现在可能会有一些翻转边的操作.手玩可以发现这相当于对于那条边对应的点进行一次\(rotate\)操作.然后如果这个点不是二叉树的根,那么只要先把这个点和父亲的贡献扣掉,\(rotate\)后在加上新的贡献即可;否则这个点是代表着初始情况最优操作中的一个,第一问答案要减去1,然后第二问答案先要扣掉这个点贡献和这个点子树对超级根的贡献,然后因为这个点被操作了,就相当于删掉这个点,两个儿子分别成为一个新二叉树,那么贡献加上这两个儿子子树并到超级根的贡献就好了

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<map>

#include<set>

#define LL long long

#define uLL unsigned long long 

using namespace std;

const int N=1e5+10,mod=1e9+7;

int rd()

{

    int x=0,w=1;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

map<int,int> id[N];

vector<int> e[N];

int fac[N],iac[N];

int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}

int inv(int a){return fpow(a,mod-2);}

int C(int n,int m){return m<0||n<m?0:1ll*fac[n]*iac[m]%mod*iac[n-m]%mod;}

int w,n,fa[N],ch[N][2],sz[N],size,rt[N],tp,ans=1;

void bui(int &x,int l,int r)

{

    if(l+1==r) return;

    x=id[l][r];

    sz[x]=1;

    int mid=*(--lower_bound(e[l].begin(),e[l].end(),r));

    bui(ch[x][0],l,mid),bui(ch[x][1],mid,r);

    if(ch[x][0]) fa[ch[x][0]]=x;

    if(ch[x][1]) fa[ch[x][1]]=x;

    sz[x]+=sz[ch[x][0]]+sz[ch[x][1]];

    ans=1ll*ans*C(sz[ch[x][0]]+sz[ch[x][1]],sz[ch[x][0]])%mod;

}

int main()

{

    fac[0]=1;

    for(int i=1;i<=N-10;++i) fac[i]=1ll*fac[i-1]*i%mod;

    iac[N-10]=fpow(fac[N-10],mod-2);

    for(int i=N-10;i;--i) iac[i-1]=1ll*iac[i]*i%mod;

    w=rd(),n=rd();

    for(int i=1;i<n;++i) e[i].push_back(i+1),e[i+1].push_back(i);

    e[n].push_back(1),e[1].push_back(n);

    for(int i=1;i<=n-3;++i)

    {

        int x=rd(),y=rd();

        e[x].push_back(y),e[y].push_back(x);

        id[x][y]=id[y][x]=i;

    }

    for(int i=1;i<=n;++i) sort(e[i].begin(),e[i].end());

    int nn=e[n].size(),ff=n-1-nn;

    for(int i=0;i<nn-1;++i)

    {

        int x=e[n][i],y=e[n][i+1];

        if(x+1==y) continue;

        ++tp,bui(rt[tp],x,y);

    }

    for(int i=1;i<=tp;++i)

        size+=sz[rt[i]],ans=1ll*ans*C(size,sz[rt[i]])%mod;

    printf("%d ",ff);

    if(w) printf("%d",ans);

    puts("");

    int q=rd();

    while(q--)

    {

        int x=id[rd()][rd()],na=ans;

        if(fa[x])

        {

            int yy=ch[fa[x]][1]==x;

            na=1ll*na*inv(C(sz[ch[x][0]]+sz[ch[x][1]],sz[ch[x][0]]))%mod*inv(C(sz[ch[fa[x]][0]]+sz[ch[fa[x]][1]],sz[ch[fa[x]][0]]))%mod;

            na=1ll*na*C(sz[ch[x][yy^1]]+sz[ch[fa[x]][yy^1]],sz[ch[x][yy^1]])%mod*C(sz[ch[x][yy]]+sz[ch[x][yy^1]]+sz[ch[fa[x]][yy^1]]+1,sz[ch[x][yy]])%mod;

        }

        else

        {

            na=1ll*na*inv(C(sz[ch[x][0]]+sz[ch[x][1]],sz[ch[x][0]]))%mod*inv(C(size,sz[x]))%mod;

            na=1ll*na*C(size-sz[x]+sz[ch[x][0]],sz[ch[x][0]])%mod*C(size-1,sz[ch[x][1]])%mod;

        }

        printf("%d ",ff-(!fa[x]));

        if(w) printf("%d",na);

        puts("");

    }

    return 0;

}