题目大意

给定一棵有根树，支持两种操作：

1. 查询某个节点子树中所有节点深度的第k小值。
2. 修改某条边的边权（等价于将该边下方整个子树的深度增加）。

算法分析

这个问题需要高效地处理子树查询和子树更新，核心思路是将树形结构转化为线性序列进行处理。

关键步骤

1. DFS序（欧拉序）转化

   • 对树进行DFS遍历，记录每个节点进入和离开的时间戳in[x]和out[x]
   • 节点x的子树对应DFS序中[in[x], out[x]]的连续区间
   • 这样就将树上的子树问题转化为了序列上的区间问题

2. 深度处理

   • 初始深度可以通过DFS预处理得到
   • 操作2实际上是子树深度增加操作
   • 由于len ≤ 10且操作2的k也受此限制，深度值的变化范围相对可控

3. 查询处理

   • 问题转化为：在DFS序的某个区间中查询第k小的值
   • 由于存在修改操作，需要支持动态区间第k小查询

解决方案

方法一：树状数组/线段树 + 值域分段（推荐）

• 由于深度值范围不会太大（初始深度 + 修改影响），可以对值域进行分段
• 对每个值域区间维护一个数据结构（树状数组），记录每个深度值的出现次数
• 查询时在值域上二分查找第k小的深度
• 时间复杂度：O(n log n + m log n log V)，其中V是深度值域范围

方法二：主席树（可持久化线段树）

• 在DFS序上建立主席树
• 每个版本对应DFS序的一个前缀
• 查询子树[in[x], out[x]]时，用版本out[x]减去版本in[x]-1得到子树信息
• 在值域线段树上二分查找第k小
• 时间复杂度：O((n+m) log V)

方法三：平衡树/分块

• 对每个节点维护其子树的平衡树
• 修改时更新整个子树的平衡树
• 查询时直接在第k小
• 时间复杂度较高，可能只能通过部分分

代码实现（方法一框架）

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

const int N = 100010;

int n, m, len;
vector<pair<int, int>> g[N]; // 邻接表
int in[N], out[N], timestamp; // DFS序
int depth[N]; // 节点深度
int dfs_order[N]; // DFS序列

// 树状数组部分（值域分段）
const int MAX_DEPTH = 1000010; // 最大深度估计
vector<int> tr[N]; // 值域分段的树状数组

void dfs(int u) {
    in[u] = ++timestamp;
    dfs_order[timestamp] = u;
    for (auto [v, w] : g[u]) {
        depth[v] = depth[u] + w;
        dfs(v);
    }
    out[u] = timestamp;
}

// 树状数组操作
int lowbit(int x) { return x & -x; }

void add(int tree_id, int x, int v) {
    for (; x <= n; x += lowbit(x)) {
        tr[tree_id][x] += v;
    }
}

int query(int tree_id, int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) {
        res += tr[tree_id][x];
    }
    return res;
}

// 值域映射
int get_tree_id(int depth_val) {
    // 根据深度值映射到对应的值域分段
    return depth_val / BLOCK_SIZE; // BLOCK_SIZE为分块大小
}

int main() {
    cin >> n >> m >> len;
    
    // 读入树结构
    for (int i = 2; i <= n; i++) {
        int parent, weight;
        cin >> parent >> weight;
        g[parent].emplace_back(i, weight);
    }
    
    // DFS预处理
    depth[1] = 0;
    dfs(1);
    
    // 初始化树状数组
    // 将每个节点的深度插入到对应的值域分段中
    
    while (m--) {
        int opt, x, k;
        cin >> opt >> x >> k;
        
        if (opt == 1) {
            // 查询子树第k小深度
            int l = in[x], r = out[x];
            // 在值域上二分查找第k小的深度
            // 使用树状数组统计区间内<=mid的数的个数
        } else {
            // 更新边权，相当于子树深度增加k
            int l = in[x], r = out[x];
            // 将子树区间内所有深度值增加k
            // 更新对应的值域分段树状数组
        }
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：O(n log n + m log n log V)
  • DFS预处理：O(n)
  • 每次查询/修改：O(log n log V)
• 空间复杂度：O(n log V)

总结

本题的难点在于将树上的子树操作转化为序列操作，并高效处理带修改的区间第k小查询。利用DFS序和值域分段的思路，可以在合理的时间复杂度内解决这个问题。题目背景虽然复杂，但核心是一个经典的数据结构问题。