E. Iris 的满二叉树 详细题解

问题重述

给定一棵以 $1$ 为根、按顺序添加节点的树（$p_i$ 表示 $i$ 的父节点）。定义一棵树的二叉树深度为最小的 $d$，使得可以通过添加节点和边将其变成深度为 $d$ 的满二叉树（$2^d-1$ 个节点，每个非叶子节点恰有 $2$ 个子节点）。若不存在这样的 $d$，则为 $-1$。对于每个 $i$（$1 \le i \le n$），输出前 $i$ 个节点构成的树的二叉树深度。

关键观察

引理 1：直径端点性质

树上与某点距离最远的点中，必有一个是某条直径的端点。

引理 2：合并树的直径

合并两棵树后，新直径的端点必来自原两棵树的四条直径端点中。

结论 1：根的存在性

若一棵树是 $d$-二叉树，则存在唯一节点可作为满二叉树的根，且该节点深度最小。将该节点作为根后，整棵树可以"抬高"使根深度为 $1$。

结论 2：度数限制

在满二叉树中：

• 根节点度数 $\le 2$
• 其他内部节点度数 $= 3$（一个父节点 + 两个子节点）
• 叶子节点度数 $= 1$

因此，若原树中出现度数 $\ge 4$ 的节点，则无法扩展成满二叉树，答案为 $-1$。

核心思路

1. 直径维护：动态维护当前树的直径（两个端点 $x, y$ 和长度 $len$）
2. 距离计算：对于任意节点 $z$，其到直径端点的最大距离决定了以 $z$ 为根时所需深度
3. 度数处理：度数 $\ge 3$ 的节点不能作为根，将其距离设为 $+\infty$
4. 线段树维护：用 DFS 序将子树映射到区间，支持区间加和全局最小值查询

算法步骤

第一步：预处理

• 以 $0$ 为根进行 DFS，计算每个节点的：
  • dep[x]：深度
  • dfn[x]：DFS 序编号
  • ls[x]：子树大小（用于区间表示）
  • an[x][k]：倍增祖先

第二步：直径更新

当添加新节点 $i$ 时：

• 计算 $i$ 到当前直径两端 $x, y$ 的距离
• 若新距离大于当前直径长度，则更新直径
• 同时更新"距离贡献"：对于新直径中点附近的子树，距离值需要调整

第三步：距离维护

定义 val[x] 表示以 $x$ 为根时，需要的最小满二叉树深度。实际上：

$$\text{val}[x] = \max(\text{dist}(x, \text{diam}_1), \text{dist}(x, \text{diam}_2)) + 1 $$

其中 $\text{diam}_1, \text{diam}_2$ 是直径的两个端点。

当直径更新时，val[x] 的变化可以表示为对某些子树的区间加操作。

第四步：度数限制

• 当某个节点度数达到 $3$ 时，将其 val 设为 $+\infty$（不能作为根）
• 当某个节点度数达到 $4$ 时，之后所有答案为 $-1$

第五步：答案计算

每次添加节点后，答案为：

$$\min_{x} \text{val}[x]$$

时间复杂度

• 预处理：$O(n \log n)$
• 每次操作：$O(\log n)$
• 总复杂度：$O(n \log n)$

完整代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define REP(i,b,e) for(int i=(b);i<(int)(e);++i)

const int INF = 1e18;

// 线段树维护区间最小值，支持区间加
struct SegmentTree {
    int seg[2000005], tag[2000005];
    
    void build(int l, int r, int p) {
        seg[p] = (l == 0 ? 0 : INF);
        tag[p] = 0;
        if (l == r) return;
        int m = (l + r) >> 1;
        build(l, m, p * 2 + 1);
        build(m + 1, r, p * 2 + 2);
    }
    
    void pushdown(int p) {
        if (!tag[p]) return;
        tag[p * 2 + 1] += tag[p];
        tag[p * 2 + 2] += tag[p];
        seg[p * 2 + 1] += tag[p];
        seg[p * 2 + 2] += tag[p];
        tag[p] = 0;
    }
    
    void add(int l, int r, int s, int t, int p, int val) {
        if (l <= s && t <= r) {
            seg[p] += val;
            tag[p] += val;
            return;
        }
        int m = (s + t) >> 1;
        pushdown(p);
        if (m >= l) add(l, r, s, m, p * 2 + 1, val);
        if (m < r) add(l, r, m + 1, t, p * 2 + 2, val);
        seg[p] = min(seg[p * 2 + 1], seg[p * 2 + 2]);
    }
    
    void update(int pos, int l, int r, int p, int val) {
        if (l == r) {
            seg[p] = val;
            return;
        }
        int m = (l + r) >> 1;
        pushdown(p);
        if (m >= pos) update(pos, l, m, p * 2 + 1, val);
        else update(pos, m + 1, r, p * 2 + 2, val);
        seg[p] = min(seg[p * 2 + 1], seg[p * 2 + 2]);
    }
    
    int query() { return seg[0]; }
} seg;

int n;
vector<int> v[500005];
int fa[500005], an[500005][21];
int dep[500005], dfn[500005], rev[500005];
int tot, deg[500005], ls[500005];

// DFS 预处理
void dfs(int x, int pre, int d) {
    dep[x] = d;
    fa[x] = pre;
    an[x][0] = fa[x];
    ls[x] = 1;
    
    // 倍增预处理
    for (int i = 0; i < 20; i++) {
        if (an[x][i] == -1) an[x][i + 1] = -1;
        else an[x][i + 1] = an[an[x][i]][i];
    }
    
    rev[tot] = x;
    dfn[x] = tot++;
    for (auto i : v[x]) {
        dfs(i, x, d + 1);
        ls[x] += ls[i];
    }
}

// LCA 查询
int getlca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    for (int i = 20; i >= 0; --i) {
        if ((d >> i) & 1) x = an[x][i];
    }
    if (x == y) return x;
    for (int i = 20; i >= 0; --i) {
        if (an[x][i] != an[y][i]) {
            x = an[x][i];
            y = an[y][i];
        }
    }
    return fa[x];
}

// 获取 x 在 y 方向上的子节点
int get_child(int x, int y) {
    if (dfn[y] >= dfn[x] && dfn[y] <= dfn[x] + ls[x] - 1) {
        int d = dep[y] - dep[x] - 1;
        for (int i = 0; (1 << i) <= d; ++i) {
            if ((d >> i) & 1) y = an[y][i];
        }
        return y;
    } else {
        return fa[x];
    }
}

// 更新距离：直径变化时，对子树进行区间加
void update_side(int x, int y) {
    if (dfn[y] >= dfn[x] && dfn[y] <= dfn[x] + ls[x] - 1) {
        // y 在 x 的子树中
        seg.add(0, n - 1, 0, n - 1, 0, 1);
        x = get_child(x, y);
        seg.add(dfn[x], dfn[x] + ls[x] - 1, 0, n - 1, 0, -1);
    } else {
        seg.add(dfn[x], dfn[x] + ls[x] - 1, 0, n - 1, 0, 1);
    }
}

// 计算两点距离
int get_dist(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[getlca(x, y)];
}

// 直径结构体
struct Diameter {
    int x, y, len;
    
    // 更新直径，返回新节点 i 的 val 值
    int update(int z) {
        if (x == y) {
            int d = get_dist(x, z);
            if (d <= len) return d + len;
            update_side(y, z);
            y = get_child(y, z);
            return d + len;
        } else {
            int d1 = get_dist(x, z), d2 = get_dist(y, z);
            int d3 = min(d1, d2);
            if (d3 <= len) return d3 + len + 1;
            if (d1 > d2) swap(x, y);
            update_side(y, z);
            y = x;
            ++len;
            return len * 2;
        }
    }
    
    // 查询节点 z 的 val 值
    int query(int z) {
        if (x == y) return len + get_dist(x, z);
        else return len + min(get_dist(x, z), get_dist(y, z)) + 1;
    }
};

void Main() {
    cin >> n;
    
    // 清空邻接表
    for (int i = 0; i < n; i++) v[i].clear();
    
    // 读入父节点
    for (int i = 1; i < n; i++) {
        cin >> fa[i];
        --fa[i];
        v[fa[i]].push_back(i);
    }
    
    // DFS 预处理
    tot = 0;
    dfs(0, -1, 0);
    seg.build(0, n - 1, 0);
    
    // 初始化子树区间
    for (int i = 0; i < n; i++) {
        deg[i] = 0;
        ls[i] = ls[i] + dfn[i] - 1;
    }
    
    // 输出第一个答案（只有根节点）
    cout << "1 ";
    
    Diameter d = {0, 0, 0};
    
    for (int i = 1; i < n; i++) {
        // 更新度数
        ++deg[fa[i]];
        ++deg[i];
        
        // 度数 >= 4 时，后续全部为 -1
        if (deg[fa[i]] == 4) {
            for (int j = i; j < n; j++) cout << -1 << ' ';
            cout << endl;
            return;
        }
        
        // 度数 == 3 的节点不能作为根，设为 INF
        if (deg[fa[i]] == 3) {
            seg.update(dfn[fa[i]], 0, n - 1, 0, INF);
        }
        
        // 更新新节点的 val 值
        seg.update(dfn[i], 0, n - 1, 0, d.update(i));
        
        // 输出当前全局最小值 + 1
        cout << seg.query() + 1 << ' ';
    }
    cout << endl;
}

void TC() {
    int tc = 1;
    cin >> tc;
    while (tc--) {
        Main();
        cout.flush();
    }
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    TC();
    return 0;
}

代码说明

1. DFS 预处理：计算深度、DFS 序、子树大小、倍增祖先

2. 直径维护：

   • Diameter 结构体存储当前直径的两个端点和长度
   • update(z) 添加新节点时更新直径，返回新节点的 val 值
   • query(z) 计算节点 z 到直径端点的最大距离

3. 线段树：

   • 维护每个节点的 val 值
   • 支持区间加和单点更新
   • 查询全局最小值

4. 子树区间表示：

   • 节点 x 的子树对应区间 [dfn[x], dfn[x] + ls[x] - 1]
   • 利用 DFS 序将树结构转化为区间问题

总结

本题的核心技巧：

1. 利用直径性质将问题转化为到两端点的距离
2. 动态维护直径，每次添加节点时 $O(1)$ 更新
3. 用 DFS 序将子树映射到区间，用线段树维护区间加和最小值
4. 度数限制处理：度数 $\ge 4$ 直接输出 $-1$，度数 $=3$ 的节点设为 $+\infty$
5. 总复杂度 $O(n \log n)$