还是比较小清新的一道题？我甚至找不到合适的标签（
显然终止条件就是所有边连向 \(n\)，最优策略也是每次把一条边连向 \(n\)。
所以最少次数就是开始时不与 \(n\) 相连的边的条数。
那么把和 \(n\) 相连的点（包括 \(1,n-1\)）排序后，取相邻的两个点 \(l,r\)，则必然存在，且仅存在一个点 \({\rm mid} \in (l,r)\) 与 \(l,r\) 都相连。
那么如果进行了 \((l,r)\)「旋转」便相当于把 \((l,r)\) 拆成了 \((l,{\rm mid}),({\rm mid},r)\)。
然后这样就能建出一片二叉树森林，方案数便是合并左右儿子的贡献，组合数算一下就行了。
考虑在此基础上再进行一次 \((a,b)\)「旋转」操作会有什么情况：
- \((a,b)\) 不是某棵二叉树的根。
那么这次操作并不是最优策略，不会影响步数。 而在二叉树上，相当于把 \((a,b)\) 对应的点进行一次类似平衡树的旋转操作。
注意到 \(a < b\)，并且 \(a\) 一定和 \(n\) 相连（若 \(a,b\) 都不与 \(n\) 相连则不合法），所以 \((a,b)\) 一定是左儿子。
计算此对答案的修改量并不难。 - \((a,b)\) 是某棵二叉树的根。 那么这会使步数减少一，并把一棵二叉树的根的左右子树拆开。
这也不难计算。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
const int N = 1e5;
const int mod = 1e9 + 7;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int W,n,m;
int fac[N + 5],ifac[N + 5];
int cnt,sum = 1,ans1,ans2;
vector<int> e[N + 5];
inline int C(int n,int m)
{
return n < m ? 0 : (long long)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
inline int Ci(int n,int m)
{
return n < m ? 0 : (long long)ifac[n] * fac[m] % mod * fac[n - m] % mod;
}
tr1::unordered_map< int,tr1::unordered_map<int,int> > id;
int fa[N + 5],ls[N + 5],rs[N + 5],sz[N + 5],rt;
void build(int &p,int l,int r)
{
static int tot = 0;
if(r - l == 1)
return ;
id[l][r] = p = ++tot;
int mid = *upper_bound(e[r].begin(),e[r].end(),l);
build(ls[p],l,mid),build(rs[p],mid,r),
ls[p] && (fa[ls[p]] = p),
rs[p] && (fa[rs[p]] = p),
sz[p] = sz[ls[p]] + 1 + sz[rs[p]],
sum = (long long)sum * C(sz[p] - 1,sz[ls[p]]) % mod;
}
int main()
{
scanf("%d%d",&W,&n),fac[0] = 1;
for(register int i = 1;i <= n;++i)
fac[i] = (long long)fac[i - 1] * i % mod;
ifac[n] = fpow(fac[n],mod - 2);
for(register int i = n;i;--i)
ifac[i - 1] = (long long)ifac[i] * i % mod;
int u,v;
for(register int i = 1;i <= n - 3;++i)
scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
for(register int i = 1;i <= n;++i)
e[i].push_back(i % n + 1),e[i % n + 1].push_back(i);
for(register int i = 1;i <= n;++i)
sort(e[i].begin(),e[i].end());
for(register vector<int>::iterator i = e[n].begin(),j = i + 1;j != e[n].end();++i,++j)
rt = 0,build(rt,*i,*j),sum = (long long)sum * C(cnt += sz[rt],sz[rt]) % mod;
printf("%d%c",cnt,"\n "[W]),W && printf("%d\n",sum);
for(scanf("%d",&m);m;--m)
{
scanf("%d%d",&u,&v),ans1 = cnt,ans2 = sum;
int p = id[u][v];
if(fa[p])
ans2 = (long long)ans2 * Ci(sz[p] - 1,sz[ls[p]]) % mod * Ci(sz[fa[p]] - 1,sz[p]) % mod,
ans2 = (long long)ans2 * C(sz[rs[p]] + sz[rs[fa[p]]],sz[rs[p]]) % mod * C(sz[p] + sz[rs[fa[p]]],sz[ls[p]]) % mod;
else
--ans1,
ans2 = (long long)ans2 * Ci(sz[p] - 1,sz[ls[p]]) % mod * Ci(cnt,sz[p]) % mod,
ans2 = (long long)ans2 * C(cnt - sz[rs[p]] - 1,sz[ls[p]]) % mod * C(cnt - 1,sz[rs[p]]) % mod;
printf("%d%c",ans1,"\n "[W]),W && printf("%d\n",ans2);
}
}