complete
untergehen
·
·
题解
补全一下数据结构做法。
我们考虑有悬浮叶子情况下答案怎么算。
我们尝试维护一个数组 \text{cnt[x]} 表示 x 有几个儿子与外环相连，以及点集 \text{R} 表示真根（去掉悬浮叶子后的深度最低的点）。
我们发现这两个东西就足以算出答案了（可以参考官方题解），考虑维护。
考虑对于现在的一个连通块，我们将他的所有真叶子（初始的叶子，也即与外环相连的叶子）以线段树的方式放在他的深度最低的点上。在连断边的时候可以线段树分裂合并。
考虑这个连通块有真根当且仅当其拥有至少两个真叶子，如果有的话就是其编号最小的和编号最大的真叶子的 \operatorname{LCA}。所以我们可以快速地得到真根。
我们不妨考虑连边（这里断边操作是对称的）
我们将 $x$ 连到 $y$ 上。其中 $x,y$ 均有真叶子（可以验证如果 $x$ 或 $y$ 没有真叶子则不会有需处理的变化）。我们注意 $\text{cnt}$ 唯一发生需处理变化的地方是 $x\to y$ 路径上第一个与外环相连的点（图中 $\texttt{this!}$ 所指的点）这个点的 $\text{cnt}$ 会增加 $1$（注意如果更改后的 $\text{cnt}$ 需强制 $>1$（因为我们放弃处理了 $0\to 1$））。而这个点正是 $y$ 中第一个编号比 $x$ 大的真叶子与 $x$ 的 $\operatorname{LCA}$ 和最后一个编号比 $x$ 小的真叶子与 $x$ 的 $\operatorname{LCA}$ 中较深的一个。可以线段树上二分迅速求出。
我们考虑怎么找到 $y$ 呢？可以离线使用线段树合并或在线树剖。
考虑以上的所有操作只会对 $\mathcal{O}(1)$ 个点的贡献发生修改，直接维护答案即可。
值得注意的是需维护答案因子中 $0$ 的个数，因为他没有逆元。
复杂度$\mathcal{O}(n+q\log (n+q+\text{mod}))$ 或者 $\mathcal{O}(n\log n+q(\log^2(n+q)+\log{\text{mod}}))$。
:::info[实现起来有点麻烦]
```cpp
#include<bits/stdc++.h>
#define mod 1000000007
#define N 1000005
using namespace std;
namespace shan{
typedef long long ll;
ll power(ll x,int h){
ll ans=1;
for(;h;h>>=1,x=x*x%mod)
if(h&1)ans=ans*x%mod;
return ans;
}
int inv(int x){return power(x,mod-2);}
int n,k,q,p[N],X[N];
int ivk,ivk1;
void __getx(){
X[1]=k;X[2]=(ll)k*(k-1)%mod;X[3]=(ll)k*(k-1)%mod*(k-2)%mod;
for(int i=4;i<=n;i++)
X[i]=((ll)X[i-1]*(k-2)+(ll)X[i-2]*(k-1))%mod;
ivk=inv(k);ivk1=inv(k-1);
}
int T;
int tot_node;
struct node_t{int ls,rs,lcf;}t[N<<5];
inline int n_node(){t[++tot_node]={0,0,0};return tot_node;}
inline void push_up(int x){t[x].lcf=t[t[x].ls].lcf+t[t[x].rs].lcf;}
void merge(int l,int r,int &x,int y){
if(!x||!y){x=x|y;return;}
t[x].lcf+=t[y].lcf;
int mid=(l+r)>>1;
merge(l,mid,t[x].ls,t[y].ls);
merge(mid+1,r,t[x].rs,t[y].rs);
}
void split(int l,int r,int s,int e,int &x,int &y){
if(l<=s&&e<=r){y=x;x=0;return;}
y=n_node();
int mid=(s+e)>>1;
if(l<=mid)split(l,r,s,mid,t[x].ls,t[y].ls);
if(mid<r)split(l,r,mid+1,e,t[x].rs,t[y].rs);
push_up(x);push_up(y);
}
int upper(int i,int l,int r,int x){
if(l==r||!x)return t[x].lcf?l:-1;
int mid=(l+r)>>1;
if(i<=mid&&t[t[x].ls].lcf){
int la=upper(i,l,mid,t[x].ls);
return la!=-1?la:upper(i,mid+1,r,t[x].rs);
}
return upper(i,mid+1,r,t[x].rs);
}
int lower(int i,int l,int r,int x){
if(l==r||!x)return t[x].lcf?l:-1;
int mid=(l+r)>>1;
if(mid<i&&t[t[x].rs].lcf){
int ra=lower(i,mid+1,r,t[x].rs);
return ra==-1?lower(i,l,mid,t[x].ls):ra;
}
return lower(i,l,mid,t[x].ls);
}
void build(int l,int r,int &x,int *islef){
x=n_node();
if(l==r){t[x].lcf=islef[l];return;}
int mid=(l+r)>>1;
build(l,mid,t[x].ls,islef);
build(mid+1,r,t[x].rs,islef);
push_up(x);
}
int rt[N],vis[N],cnt[N];
int ans,cnt0,mxr[N];
void push(int x){if(x)ans=(ll)ans*x%mod;else cnt0++;}
void del(int x){if(x)ans=(ll)ans*inv(x)%mod;else cnt0--;}
int st[20][N],islf[N],rtat[N];
int LCA(int x,int y){
if(x==y)return x;
if(x>y)swap(x,y);
int len=__lg(y-x);
return min(st[len][x+1],st[len][y-(1<<len)+1]);
}
void pushA(int x){push((ll)X[cnt[x]]*ivk%mod);}
void delA(int x){del((ll)X[cnt[x]]*ivk%mod);}
void pushB(int x){push((ll)X[cnt[x]+1]*ivk%mod*ivk1%mod);}
void delB(int x){del((ll)X[cnt[x]+1]*ivk%mod*ivk1%mod);}
void getpre(){
ans=k;cnt0=0;tot_node=0;
for(int i=1;i<=n;i++)st[0][i]=p[i];
for(int l=1;l<=__lg(n);l++)
for(int i=1;i+(1<<l)-1<=n;i++)
st[l][i]=min(st[l-1][i],st[l-1][i+(1<<(l-1))]);
build(1,n,rt[1],islf);
for(int i=2;i<=n;i++)if(cnt[i])pushB(i);
pushA(1);
cout<<(cnt0?0:ans)<<'\n';
}
void AtoB(int x){delA(x),pushB(x);}
void BtoA(int x){delB(x),pushA(x);}
int _x[N],_y[N];
set<int>h[N];vector<int>cg[N];
signed main(){
cin>>T;
while(T--){
cin>>n>>k>>q;
__getx();
for(int i=1;i<=n;i++)islf[i]=1,cnt[i]=vis[i]=0;
for(int i=2;i<=n;i++)
cin>>p[i],islf[p[i]]=0,cnt[p[i]]++,mxr[i]=i;
for(int i=n;i>=2;i--)
mxr[p[i]]=max(mxr[p[i]],mxr[i]);
vis[1]=1;rtat[1]=1;
getpre();
for(int i=1;i<=n;i++)h[i].clear(),cg[i].clear();
for(int i=1;i<=q;i++)
cin>>_x[i],h[p[_x[i]]].insert(i),cg[_x[i]].push_back(i),_y[i]=1;
for(int i=n;i>=1;i--){
for(int j=0;j<(int)cg[i].size();j+=2){
int nxt=j+1<(int)cg[i].size()?cg[i][j+1]:q+1;
auto it=h[i].lower_bound(cg[i][j]);
while(it!=h[i].end()&&*it<nxt)
_y[*it]=i,it=h[i].erase(it);
}
if(!p[i])continue;
if(h[p[i]].size()<h[i].size())h[p[i]].swap(h[i]);
for(auto j:h[i])h[p[i]].insert(j);
h[i].clear();
}
for(int _=1;_<=q;_++){
int x=_x[_],y=_y[_];
if(vis[x]){
if(t[rt[x]].lcf&&t[rt[y]].lcf){
int at=max(LCA(x,upper(x,1,n,rt[y])),LCA(x,lower(x,1,n,rt[y])));
if(at==rtat[y]){
delA(at);
cnt[at]++;
pushA(at);
}else{
if(cnt[at])delB(at);
cnt[at]=max(2,cnt[at]+1);
pushB(at);
}
}
if(rtat[x])AtoB(rtat[x]);
if(rtat[y])AtoB(rtat[y]);
merge(1,n,rt[y],rt[x]);
if(t[rt[y]].lcf>=2)
rtat[y]=LCA(upper(1,1,n,rt[y]),lower(n,1,n,rt[y])),BtoA(rtat[y]);
vis[x]=0;
}else{
if(rtat[y])AtoB(rtat[y]);
rtat[y]=rtat[x]=0;
split(x,mxr[x],1,n,rt[y],rt[x]);
if(t[rt[y]].lcf>=2)
rtat[y]=LCA(upper(1,1,n,rt[y]),lower(n,1,n,rt[y])),BtoA(rtat[y]);
if(t[rt[x]].lcf>=2)
rtat[x]=LCA(upper(1,1,n,rt[x]),lower(n,1,n,rt[x])),BtoA(rtat[x]);
if(t[rt[x]].lcf&&t[rt[y]].lcf){
int at=max(LCA(x,upper(x,1,n,rt[y])),LCA(x,lower(x,1,n,rt[y])));
if(at==rtat[y]){
delA(at);
cnt[at]--;
pushA(at);
}else{
delB(at);
cnt[at]--;
pushB(at);
}
}
vis[x]=1;
}
cout<<(cnt0?0:ans)<<'\n';
}
}
return 0;
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
shan::main();
return 0;
}
```
:::