对原树进行轻重链剖分；

假设当前在处理以 $w$ 为根的大小为 $n$ 的子树，且 $w$ 是重链头，当前莫队状态为 $w$ 的子树补。可以在 $O(n)$ 时间扫出 $w$ 所在重链上，每个结点的子树补（这部分总代价为$O(n \log n)$）；

然后将w所在重链的每个点的轻儿子找出来，之后要递归处理；

将这些轻儿子按子树大小加权，以及重链上每个点按 $1$ 加权，建哈夫曼树，在哈夫曼树上dfs，维护哈夫曼树上当前点的子树补，到达叶子时若叶子对应轻儿子则递归处理轻子树。将整个递归过程中，产生的哈夫曼树拼接起来，得到所有叶子权为 $1$ 的哈夫曼树，由于哈夫曼树上，每向下两层子树权值和至少减小一个常数比例，由此得到遍历哈夫曼树过程的莫队的复杂度是 $O(n\log n)$ 的。

因此总时间 $O(n\log n)$。

使用轻重链剖分

1. 对根所在重链，可以在n次插入得到重链上每个点的答案，
2. 轻子树需要建立哈夫曼树，叶子的权重为子树规模，重链也作为一个叶子，权重为重链长度；

在哈夫曼树上dfs，维护当前子树外对应的集合，移动到叶子时就递归到了轻子树上的子问题，所需插入次数为所有非叶结点的子树规模之和（子树规模为子树中叶结点的权重之和）；

#include<bits/stdc++.h>
const int maxn=1e5,N=maxn+7,inf=1e9+7;
std::mt19937 mt(time(0));//
int read(int L,int R){
    //return L+mt()%(R-L+1);//
    int x;
    assert(scanf("%d",&x)==1);
    assert(L<=x);
    assert(x<=R);
    return x;
}
int fa[N],in[N],q[N],ql,qr,son[N],sz[N],n,m,ch[N*2][2],cp;
std::vector<int> e[N];
void hld(){
    for(int i=1;i<=n;++i)in[i]=0,sz[i]=1,son[i]=0;
    for(int i=1;i<=n;++i)++in[fa[i]];
    ql=qr=0;
    for(int i=1;i<=n;++i)if(!in[i])q[++qr]=i;
    while(ql!=qr){
        int w=q[++ql],f=fa[w];
        if(!f)continue;
        if(!--in[f])q[++qr]=f;
        sz[f]+=sz[w];
        if(sz[w]>sz[son[f]])son[f]=w;
    }
    //for(int i=1;i<=n;++i)printf("%d:%d\n",i,son[i]);
    ql=qr=0;
    cp=n;
}
int ins_cnt=0,undo_cnt=0,pos;
char otpt[8*5500000+1000000];
int temp[10];
void out(int u){
    //if( u > 100000 ) std :: cerr << u << std :: endl;
    static int *q=temp;
    if(!u) otpt[pos++]='0';
    else
    {
        while(u)
        {
            int b=u/10;
            *q++=u-b*10+'0';
            u=b;
        }
        while(q!=temp)
            otpt[pos++]=*--q;
    }
}
void chk(int w){
    //printf("%d: ",w);
    //for(int i=1;i<=qr;++i)printf("(%d)",q[i]);puts("");
    otpt[pos++]='=';
    out(w);
    assert(qr==n-sz[w]);
}
void ins(int w){
    //printf("+%d\n",w);
    ++ins_cnt;
    otpt[pos++]='+';
    out(w);
    q[++qr]=w;
}
void undo(int q0){
    //printf("-%d\n",q0);
    while(qr!=q0)
    {
        qr--;
        otpt[pos++]='-';
    }
    ++undo_cnt;
    ql=qr;
}
struct Pos{
    int x,sz;
    bool operator<(const Pos&w)const{return sz<w.sz;}
}ps1[N],ps2[N];
int pp1,pp2;
struct Undo{
    int l;
    Undo():l(qr){}
    ~Undo(){undo(l);}
};
void bfs(){
    while(ql!=qr){
        int v=q[++ql];
        for(int x:e[v])ins(x);
    }
}
void dfs(int w);
void dfs3(int w){
    //printf("dfs3 %d\n",w);
    if(w<=n)return ins(w);
    dfs3(ch[w][0]);
    dfs3(ch[w][1]);
}
void dfs2(int w,int u=0){
    //printf("dfs2 %d(%d %d) %d\n",w,ch[w][0],ch[w][1],u);
    Undo _;
    if(u){
        ql=qr;
        dfs3(u);
        bfs();
    }
    if(w<=n)return dfs(w);
    int lc=ch[w][0],rc=ch[w][1];
    dfs2(lc,rc);
    dfs2(rc,lc);
}
void dfs(int w){
    pp1=pp2=0;
    {
        Undo _;
        for(int u=w;u;){
            chk(u);
            int nx=son[u];
            ins(u);
            ql=qr;
            for(int x:e[u])if(x!=nx){
                ins(x);
                ps1[pp1++]=Pos{x,sz[x]};
            }
            bfs();
            u=nx;
        }
    }
    if(!pp1)return;
    std::sort(ps1,ps1+pp1);
    ps1[pp1].sz=inf;
    ps2[pp2].sz=inf;
    int cnt=pp1,p1=0,p2=0;
    for(;;){
        Pos a=(ps1[p1]<ps2[p2]?ps1[p1++]:ps2[p2++]);
        if(!--cnt){
            Undo _;
            for(int u=w;u;u=son[u])ins(u);
            return dfs2(a.x);
        }
        Pos b=(ps1[p1]<ps2[p2]?ps1[p1++]:ps2[p2++]);
        ps2[pp2++]=Pos{++cp,a.sz+b.sz};
        ps2[pp2].sz=inf;
        ch[cp][0]=a.x;
        ch[cp][1]=b.x;
    }
}
int main(){
    //freopen( "data1.in" , "r" , stdin );
    //freopen( "data1.out" , "w" , stdout );
    n=read(1,maxn);
    //n=10;
    for(int i=2;i<=n;++i){
        int f=fa[i]=read(1,i-1);
        //printf("%d\n",f);
        e[f].push_back(i);
    }
    hld();
    dfs(1);
    //fprintf(stderr,"%d %g %g\n",n,ins_cnt*1./(n*log2(n)),undo_cnt*1./n);
    otpt[pos++]='!';
    fwrite( otpt , 1 , pos , stdout );
    return 0;
}

题目非私密模拟，可以公开博客。

Problem 1

取 $G$ 的任一 DFS 树 $T$，考虑一条边 $(u,v) \in E$ 且 $d_u > d_v$，由于 DFS 树中没有横叉边，因此 $u \in \mathrm{subtree}(v)$，考虑删去 $u,v$ 后整棵树会分成以下几个部分：

• $v$ 到根以及上面挂着的部分，记作 $H$。
• $u$ 到 $v$ 路径及上面挂着的部分，记作 $M$。
• $u$ 的所有子树，记作 $L_i$。

问题等价于判断这些部分有没有全部被连在一起。

首先，判断 $H$ 和 $M$ 有没有被连起来是简单的：预处理 $u$ 到其 $2^k$ 次祖先的这一段以及上面挂着的东西中，不算 $u$，连出去的边最高能到哪里。如果这个深度突破了 $v$，那么 $H$ 和 $M$ 就连起来了。

然后考虑 $H$ 和 $L_i$ 的连接。这个也是简单的：DFS 的时候预处理出每个子树里面，连上去最高到哪里，如果突破了 $v$ 就说明连起来了。因此，我们可以把所有边按照 $u$ 分类，然后按照 $v$ 从深到浅的顺序考虑，那么每个 $L_i$ 就会逐渐地和 $H$ 连起来，扫描线即可。

最后就是 $M$ 和 $L_i$。既然我们之前已经按照 $v$ 从深到浅考虑了，所以只要求出 $v$ 深度的临界点即可。这个可以通过将所有 $u$ 按照从浅到深的顺序考虑，然后用一个线段树来查询每个子树往上，最深连到了哪里。

注意几个特殊情况：$H = \varnothing$（$v$ 是根），$M = \varnothing$（$v$ 是 $u$ 的父亲）和都是空的。前面两个都可以直接处理；都是空的的情况分类讨论一下就好了，因为这个时候可能会有不在 $H,M,L_i$ 中的子树。

时间复杂度 $\Theta(n \log n)$

Problem 2

平方运算相当于指数乘二，因此其循环节长度的 $\operatorname{lcm}$ 为 $2^x \pmod {998244352}$ 的循环节长度。

$998244352=7\times 17 \times 2^{23}$，其循环节长度应该很短，具体跑一下发现循环节长度为 $24$。

使用线段树维护，对于一个 $a_i$，如果它当前不在循环节上（$a_i$ 的变化可能是 $\rho$ 型的），那么可以暴力修改。

否则线段树上每个区间维护一个长为 $24$ 的环，每次平方就将环往前转一格即可。复杂度 $\Theta(cq log n)$，其中 $c=24$。

Problem 3

利用给定条件不难求出树的质心 $c$（可以将每条边看做质量在中点处然后求加权平均），转动惯量 $I$（中点距离质心 $d$ ，长度 $l$ 的边的转动惯量为 $I=\frac{1}{12}\eta l^3 + \eta ld^2$ ，然后对所有边求和）和外力矩 $M$ （设质心到边中点矢量为 $r$，则这条边的力矩为 $r \times f_i$，其中为 $\times$ 向量外积，然后对所有边求和），并求出角加速度 $\beta=M/I$，进而得到初始角度 $\theta=\frac{1}{2}\beta t^2$ 和角初速度 $\omega=-\beta t$，并得到时刻 $T$ 的角度 $\theta_T = \frac{1}{2}\beta(t-T)^2$。

对于树质心的运动，求出结束时加速度 $a_t = F_t/M = r(\cos \theta, \sin \theta)$，则时刻 $T$ 的加速度为 $a_T = r(\cos(\theta + \frac{1}{2} \beta(t-T)^2), \sin(\theta + \frac 12 \beta(t-T)^2))$，由于初始时质心速度为 $0$ ，则质心在这段时间的位移量为：

$$\int_0^t \int_0^x a_T \mathrm d T \mathrm dx = -\frac 12 \int_{t^2}^0 r(\cos(\theta+\frac 12\beta\alpha), \sin(\theta+\frac 12\beta\alpha)) \mathrm d\alpha$$

最后的积分根据 $\beta$ 是否为 $0$ 讨论后可以求出。

于是问题得到了解决，时间复杂度 $\Theta(n)$。

Problem 4

容易将问题分成两个部分：第一部分找出 $A$ 的数的集合，而第二部分找出 $A$ 的顺序。考虑到给出的次数限制，平均每一次询问我们需要利用到超过一位的信息，首先考虑找出集合的部分，我们可以将每个数标为 $0$ 或 $1$，那么每次操作即是求不超过 $M$ 个数之和。

考虑一个经典问题，给定 $L$ 个数构成的 $0/1$ 串，如何通过查询子集和确定该串中每个位置的取值，朴素的解法需要查询线性次，而实际上我们可以构造出查询 $O(\frac{L}{\log L})$ 次的方法：不妨假设我们能用 $a - 1$ 次询问和 $1$ 次额外的询问总和的操作得出长度为 $b$ 的序列的取值，我们就可以用 $2a - 1$ 次询问和 $1$ 次额外的询问总和的操作得出长度为 $2b + a − 1$ 的序列的取值。

这是通过先查询前 $b$ 个数的和 $s$，随后对于每一个用来查询长度为 $b$ 的序列的询问，不妨假设其在前 $b$ 个位置的和为 $u$，接下来的 $b$ 个位置和为 $v$，我们分别查询 $s - u + v$ 和 $u + v$，容易发现此时我们在第二次询问中还可以额外多查询一个位置的值，仍然可以还原 $u$ 和 $v$，因此我们就可以多询问出 $a - 1$ 个位置的值了，这样递推下去便是一个 $O(\frac{L}{\log L})$ 次查询的方法。而对于任意长的给定序列，我们可以将其拆成若干小段来进一步减少所需的次数。在本题中，有一个分值较大的测试点便是给这一部分解法（第二部分采取暴力方法）。

经过思考可以看出，当前问题下的最本质不同是一个随机位置是 $0$ 和 $1$ 的概率是不同的，因此直接采取上述方法会浪费许多次数。

然而，如果我们能够将长度为 $N$ 的序列切成若干段，每段恰包含一个 $1$，那么每一段中随机选一个子集值为 $0$ 和 $1$ 的概率就均等了，而我们一开始随机均等划分每个长度为 $M$ 的段只需要 $O(N/M)$ （期望情况下常数在 2.3 以内）次即可得到若干这样的段。在朴素的情况下，我们对于每一段都需要二分。然而实际上，由于每一段二分时概率均等，我们可以利用经典的求 $0/1$ 序列方法进行优化，即对二分的过程进行并行。经过简单分析，这样可以在这一部分做到 $M \log \log M$ 级别的询问次数。在这一部分，还有一个小的常数优化是我们可以每次选择长度不超过 $2M$ 的序列，在每次询问时只需询问元素个数较小的一侧即可（我们总要询问总和）。

有了以上铺垫，第二部分也可以用 $M \log \log M$ 次询问次数解决了：对于第二部分，我们可以一层层二分每个元素对应的位置，每次将所有可能的位置减半填上该元素。由于每个位置对应恰好一个元素，在每一层我们总能用元素将询问的位置填满，这样在自上至下的第 $i$ 层就是询问长度为 $2^i$ 的 $0/1$ 序列的元素值。略微精细的实现有助于减少最终所需的询问次数。

固定 $m,k$, 令 $[x^t]P(x)$ 表示 $n=t$ 时的答案，令 $[x^t]Q(x)$ 表示满足以下条件的字符串 $S$ 个数： 能通 过 $t$ 次操作消完且不能划分成 $S_1S_2$ 满足 $S_1,S_2$, 分别能用 $a,t-a$, 次消完（其中 $0 < a < t$）。易证这等价于 $S$ 不存在能通过若干次操作消完且长度在 (0,|S|)$ 的前（后）缀。显然我们有：

$$\begin{cases} P(z) &= \frac{1}{1-Q(z)}\\ Q(z) &= mzP^{k-1}(z) - \frac{1}{m}P(z)Q^2(z) \end{cases}$$

即

$$1-\frac{1}{P(z)} = mzP^{k-1}(z) - \frac{1}{m} P(z) \left(1-\frac 1{P(z)}\right)^2$$

直接进行牛顿迭代，可以得到 $40$ 分。

记 $\mathcal P=P-\mathcal E$，使用 Lagrange 反演可知：

$$[z^n] \mathcal P(z) = [z^{n-1}] \frac{m}{(1-mz)^2(1-(m-1)z)^{n(k-1)}}$$

我们的答案 $I$ 即为：

$$\begin{split} I &= \frac{1}{n} \sum_{i=0}^{n-1} (n-i) \binom{n(k-1)+i-1}{i}m^{n-i}(m-1)^i\\ &= \sum_{i=0}^{n-1} \binom{n(k-1)+i-1}{i}m^{n-i}(m-1)^i-\sum_{i=0}^{n-1} (k-1)\binom{n(k-1)+i-1}{i-1}m^{n-i}(m-1)^i \end{split}$$

两侧都是容易计算的形式，直接暴力 $\Theta(nk)$ 计算可以得到额外的 $40$ 分。使用 Lucas 定理结合数位 dp 即可在 $\Theta(p \log n+p \log k)$ 的时间复杂度内完成，得到 $100$ 分。

Subtask 1(5 points)

直接暴力建树，写基环树 dp，或者发现答案只与环长有关都可以拿到这档部分分，复杂度 $\Theta(n^3 A)$。

Subtask 2(30 points)

由Subtask1（或者其它手段），我们发现答案只与环长有关，具体来讲考虑确定了环的方案后，树上的点只有一个限制就是不与父亲相同，所以树上点的方案就是直接乘 $k-1$。

而这棵基环树的环长就是 $A \cdot (d(s,t)+1)$，所以可以枚举 $s,t$ 求距离，求完距离之后可以用矩阵快速幂求出环长为 $len$ 的答案，注意这里不同的环长最多只有 $\Theta(n)$ 种，所以把环长相同的放到一起算即可。

如何矩阵快速幂？我们设 $[\begin{matrix} f_{i,0} & f_{i,1} \end{matrix}]$ 表示链长为 $i$ 的链尾的颜色与链头是否相同的染色方案数，每当链长度加一就相当于我们给 $[\begin{matrix} f_{i,0} & f_{i,1} \end{matrix}]$ 乘上转移矩阵 $\mathbf M = \left[\begin{matrix} 0 & k - 1 \\ 1 & k - 2 \end{matrix}\right]$ 得到 $[\begin{matrix} f_{i+1,0} & f_{i+1,1} \end{matrix}]$，所以递推矩阵应该是这样：$[\begin{matrix} 1,0 \end{matrix}] \times \mathbf M^n$，不同的长度只有 $\Theta(n)$ 种，每次暴力计算，复杂度 $\Theta(n^2+b^3n \log A)$，其中 $b$ 为转移矩阵的阶。

Subtask 3(25 points)

因为要求出树上任意两点间的距离，对每个距离都要求出数量，所以我们会很自然的想到树上点分治+FFT/NTT，但 是这个模数很黑，它只有 $14$ 次单位根 $\omega_{14}$，所以 NTT 是不可行的，而 FFT 精度会出问题（这个点 比较小也许不会出问题），所以只能 MTT，总复杂度 $\Theta(n \log^2 n + b^3 n \log A)$。

Subtask 4(40 points)

因为我们要求的并不是距离而是矩阵，所以考虑把求距离和矩阵乘法两部分合到一起做。

设 $1$ 为根，，设 $\mathbf G_x$ 表示 $x$ 子树中的所有点到 $x$ 的矩阵之和，即：

$$\mathbf G_x=\sum_{y \in \mathrm{subtree}(x)} \mathbf M^{A \cdot (d(x,y)+1)} (k-1)^{A(n-d(x,y)-1)}$$

那么所有 $s=x,t\in \mathrm{subtree}(x)$ 的贡献我们就一并统计了，此时 $G_1$ 就是 $s=1$ 的答案。$G_x$ 的转移式也很好写出：

$$\mathbf G_x=\frac{1}{(k-1)^A}\left(\sum_{y \in \mathrm{son}(x)} \mathbf G_y + \mathbf I \times (k-1)^{An}\right) \times \mathbf M^A$$

其余点的贡献可以直接换根 dp 求出。时间复杂度 $\Theta(b^3n)$。