题目：https://loj.ac/problem/3056
只会写暴搜。用哈希记忆化之类的。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=,M=1e6+,bs=,md=1e9+,mod=1e9+,INF=M;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;} int W,n,lm,tot;
struct Dt{
int x,y;
Dt(int x=,int y=):x(x),y(y) {}
bool operator< (const Dt &b)const
{return x==b.x?y<b.y:x<b.x;}
bool operator== (const Dt &b)const
{return x==b.x&&y==b.y;}
}c[M];
struct Node{
Dt a[N];
void sort(){std::sort(a+,a+lm+);}
int hs()
{
int ret=;
for(int i=;i<=lm;i++)
{
ret=((ll)ret*bs+a[i].x)%md;
ret=((ll)ret*bs+a[i].y)%md;
}
return ret;
}
}s[N];
map<int,int> mp;
Node cz(Node u,Dt k)
{
int a=k.x,b=,c=k.y,d=;
for(int i=;i<=lm;i++)
{
Dt tp=u.a[i]; if(tp.x>a)break;
if(tp.x==a&&tp.y<c)b=tp.y;
if(tp.x==a&&tp.y>c&&!d)d=tp.y;
}
if(!b) b=a+;
if(!d)
{
int ty=;
for(int i=;i<=lm;i++)
if(u.a[i].x==a){ty=u.a[i].y;break;}
if(ty<a) d=ty; else d=(a==?n:a-);//ty<a!!!
}
if(b>d){u.a[].x=;return u;}///
for(int i=;i<=lm;i++)
{
Dt tp=u.a[i]; if(tp.x!=a||tp.y!=c)continue;
u.a[i].x=b; u.a[i].y=d;
for(int j=i+;j<=lm;j++)
if(u.a[j]<u.a[j-])swap(u.a[j],u.a[j-]);
for(int j=i-;j;j--)
if(u.a[j+]<u.a[j])swap(u.a[j],u.a[j+]);
}
return u;
}
Dt dfs(Node cr)
{
int h=cr.hs(); if(mp.count(h))return c[mp[h]];
Dt lj=Dt(INF,);
for(int i=;i<=lm;i++)
{
if(cr.a[i].y==n)continue;
Node to=cz(cr,cr.a[i]); if(!to.a[].x)continue;
Dt d=dfs(cz(cr,cr.a[i])); d.x++;
if(d.x==lj.x)lj.y=upt(lj.y+d.y);
else if(d.x<lj.x)lj=d;
}
if(lj.x==INF)lj=Dt(,);
mp[h]=++tot; return c[tot]=lj;
}
void solve()
{
lm=n-;
for(int i=,u,v;i<=lm;i++)
{
u=rdn(); v=rdn(); if(u>v)swap(u,v);
s[].a[i]=Dt(u,v);
}
s[].sort();
int m=rdn();
for(int i=,u,v;i<=m;i++)
{
u=rdn();v=rdn(); if(u>v)swap(u,v);
s[i]=cz(s[],Dt(u,v));
}
dfs(s[]);
for(int i=;i<=m;i++)
{
Dt d=c[mp[s[i].hs()]];
if(!W)printf("%d\n",d.x);
else printf("%d %d\n",d.x,d.y);
}
}
int main()
{
W=rdn(); n=rdn();
if(n<=)solve();
return ;
}
应该更大胆一些。果然就是最终每条边都与 n 点相连、每次能把一条边变成这样。
那么第一问的答案就是 ( n-3 ) - ( 初始就与 n 相连的边数 ) 。
并且这样的话，可以看出一个二叉树森林。就是把一条边旋转成与 n 相连之后，分出两个部分，两个部分里的边在该边旋转之后才能旋转。
设这条边的左孩子有 a 步、右孩子有 b 步，自己的方案就是 \( dp[ ls ] * dp[ rs ] * \binom{a+b}{a} \) 。 m=0 的这样做一下就行了。
一开始旋转一条边是 rotate 操作。（从“出现的边是什么”的角度来看，确实是 rotate）
如果旋转的是某个二叉树的根，就是令答案步数 -1 ， 把该二叉树从根断成两个二叉树。
如果旋转的不是根，发现对上面的影响只有 \( dp[ ] \) 的改变，所以除掉原来的再乘上现在的。
如果旋转的是根，不仅 \( dp[ ] \) 变了，一些 \( \binom{a+b}{a} \) 也变了，所以不能除掉再乘。维护前缀和后缀答案即可。
把边按 “左端点递增、右端点递减” （左端点指标号小的点）排序，找森林结构的时候，对于边的区间 [ L , R ] ， L 是第一个要旋转的，然后左端点在 L 的右端点之前（严格）的边是自己的左孩子，其他是右孩子。找分界的时候自己用了 lower_bound ，反正每次剥掉一个 L ，一共调用 n 次 lower_bound ，而且调用的数组大小还会变小，所以复杂度还可以。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=1e5+,mod=1e9+;
int pw(int x,int k)
{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;} int n,fa[N],c[N][],sta[N],top,rk[N],jc[N],jcn[N],ans;
struct Node{
int x,y;
Node(int x=,int y=):x(x),y(y) {}
bool operator< (const Node &b)const
{return x==b.x?y>b.y:x<b.x;}
}ed[N],dp[N],pr[N],sc[N];
int C(int n,int m){return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;}
Node mrg(Node u,Node v)
{ u.y+=v.y; u.x=(ll)u.x*v.x%mod*C(u.y,v.y)%mod; return u;}
void pshp(int cr)
{
dp[cr]=Node(,);
if(c[cr][])dp[cr]=mrg(dp[cr],dp[c[cr][]]);
if(c[cr][])dp[cr]=mrg(dp[cr],dp[c[cr][]]);
dp[cr].y+=(cr!=);
}
void ini_dfs(int L,int R)
{
if(L==R){pshp(L);return;}
if(ed[L+].x!=ed[L].x)
{
ini_dfs(L+,R);
c[L][]=L+; fa[L+]=L; pshp(L); return;
}
Node d=Node(ed[L+].y,n+);
int mid=lower_bound(ed+L+,ed+R+,d)-ed;
ini_dfs(L+,mid-); c[L][]=L+; fa[L+]=L;
if(mid<=R){ ini_dfs(mid,R); c[L][]=mid; fa[mid]=L;}
pshp(L);
}
void init()
{
jc[]=;for(int i=;i<=n;i++)jc[i]=(ll)jc[i-]*i%mod;
jcn[n]=pw(jc[n],mod-);
for(int i=n-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;//before!!! int lm=n-;
sort(ed+,ed+lm+);
for(int i=,lst=;i<=lm;i++)
{
while(i<=lm&&ed[i].y!=n)i++;
if(lst<i)
{
ini_dfs(lst,i-);
sta[++top]=lst; rk[lst]=top;
pr[top]=mrg(pr[top-],dp[lst]);
}
if(i<=lm)///way:1, siz:0
{
sta[++top]=i; rk[i]=top;
pr[top]=mrg(pr[top-],dp[i]);
}
lst=i+;
}
for(int i=top;i;i--)sc[i]=mrg(sc[i+],dp[sta[i]]);
}
int rotate(int x)
{
int y=fa[x],d=(x==c[y][]);
Node nx=dp[x], ny=dp[y]; c[y][d]=c[x][!d]; c[x][!d]=y;
pshp(y); pshp(x);
int ret=(ll)dp[].x*pw(ny.x,mod-)%mod*dp[x].x%mod;
c[x][!d]=c[y][d]; c[y][d]=x; dp[x]=nx; dp[y]=ny;
return ret;
}
int main()
{
int W=rdn(); n=rdn(); int lm=n-;
for(int i=,u,v;i<=lm;i++)
{ u=rdn();v=rdn();if(u>v)swap(u,v);ed[i]=Node(u,v);}
ans=lm;
for(int i=;i<=lm;i++)if(ed[i].y==n)ans--;
init(); dp[]=pr[top];
if(!W)printf("%d\n",ans);
else printf("%d %d\n",ans,dp[].x);
int m=rdn();
for(int i=,u,v,k;i<=m;i++)
{
u=rdn();v=rdn();if(u>v)swap(u,v);
k=lower_bound(ed+,ed+lm+,Node(u,v))-ed;
if(!fa[k])
{
Node d=mrg(pr[rk[k]-],sc[rk[k]+]);
if(c[k][])d=mrg(d,dp[c[k][]]);
if(c[k][])d=mrg(d,dp[c[k][]]);
if(!W)printf("%d\n",ans-);
else printf("%d %d\n",ans-,d.x);
}
else
{
if(!W)printf("%d\n",ans);
else printf("%d %d\n",ans,rotate(k));
}
}
return ;
}