题解：P17144 [NOI 2026] 木棉（暂无数据）

· · 题解

这篇题解是 0-\text{indexed} 的。

首先，已知 Prüfer 序列如何构造树：

令 n 为树的节点数。在序列最后加一个 n-1（最后两个节点也进行提示中的操作）。则以 n-1 为根，序列的每一个元素是某个节点的父亲。接下来我们确定每个元素对应的儿子是谁。除了根以外，每个节点是叶子的充要条件是存在于剩下的树中且没有儿子。那么，从 Prüfer 序列到树的构造算法就显而易见：

代码：

vector<int>get_tree(vector<int>prufer)
{
    int n=prufer.size()+2;
    vector<int>parent(n-1);
    prufer.push_back(n-1);
    vector<int>deg(n);
    for(int x:prufer)deg[x]++;
    priority_queue<int,vector<int>,greater<int>>p;
    for(int i=0;i<n;i++)if(!deg[i])p.push(i);
    for(int x:prufer)
    {
        int y=p.top();p.pop();
        parent[y]=x;
        if(!--deg[x])p.push(x);
    }
}

显然有 O(nq\log n) 做法，20 分。

接下来考虑如何回答询问。容易找到 x,y 最后一次当父亲的位置，那么就只剩下一种可能的父子关系（最后一次靠前的是儿子），注意特判树根。不妨设儿子为 x，只需找到 x 的父亲，判一下是否为 y 即可。

观察内层循环的堆，每次 pop 一次，push 0\sim 1 次，用数学归纳法易证：每次 pop 之后，已经 pop 掉的元素全部小于堆中剩余元素。

从前往后考虑 Prüfer 序列中 x 什么时候已经成为儿子：

设原序列中 a_i 下一个同样的数的下标为 nxt_i，设 x 在区间 [l,r) 中最后一次出现是在 las_i，即在区间 [las_i+1,r) 中找出最小的 i 使得：

x-\sum_{j=i}^{r-1}[nxt_j\ge r\space \land \space a_j<x]\space \le i-l

显然这个式子对一个后缀成立，从后向前扫是 O(nq)，有 52 分。

考虑优化，先离线掉 x 这一维（询问按交换后的 x 排序，然后按 a 从小到大插入并双指针），然后在原序列上按块长 =L 分块，每块一个值域树状数组维护 \forall v,nxt<v 的数量。插入显然，查询暴力跳转，大块查树状数组，散块直接判断，时间复杂度 O(n\log n+nq\log n/L+qL)。取 L=\sqrt{n\log n} 得 O(n\log n+q\sqrt{n\log n})。

考场上取 L=1024，常数极小，用时 0.523 秒。