题目分析
本题要求从初始空邻域 $N(1,0)$ 出发，通过一系列操作到达给定的 $m$ 个有向邻域 $N(x_i,y_i)$，操作总代价不超过 $2.5\times 10^9$，且操作次数不超过 $5m$。

关键观察

• 有向邻域 $N(x,y)$ 包含以 $x$ 为根的子树中距离 $x$ 小于 $y$ 的所有顶点
• 操作1只能向更大的邻域移动（集合包含关系）
• 操作2可以撤销操作1，形成类似“回溯”的机制
• 需要高效遍历树结构并访问所有目标邻域

算法思路
核心思想：树分块 + 邻域分类处理

状态设计

• 将树分成若干簇（cluster），每个簇大小约 $\sqrt{n}$
• 对每个顶点维护：
  • id[x]：DFS序编号
  • dep[x]：深度
  • down[x]：簇内最深的代表节点
  • bl[x]：所属簇编号
  • flag[x]：是否在簇边界

算法流程

1. 树分块预处理

void dfs(int x) {
    tmp[++tot] = x, id[x] = tot, dep[x] = dep[fa[x]] + 1;
    
    // 初始化根节点
    if (x == 1) cnt = flag[x] = bl[x] = 1;
    
    // 处理子节点
    for (auto v : q[x]) {
        dfs(v), siz[x] += siz[v];
        if (down[x] && down[v]) 
            down[x] = n + 1;  // 冲突标记
        else 
            down[x] |= down[v];
    }
    
    // 达到分块条件时创建新簇
    if (down[x] == n + 1 || siz[x] > B || x == 1) {
        siz[x] = 0, down[x] = x;
        int l = id[x] + 1, y = 0, sz = 0;
        
        for (auto v : q[x]) {
            if (sz + siz[v] > B || (y && down[v]))
                add_cluster(x, y, l, id[v] - 1), y = sz = 0, l = id[v];
            sz += siz[v], y |= down[v];
        }
        add_cluster(x, y, l, tot), tot = id[x];
    }
    siz[x]++;
}

2. 邻域分类处理 将目标邻域分为三类：

• 零距离邻域 ($y=0$)：直接处理
• 非簇内邻域 (!flag[x])：直接操作到达
• 簇内邻域：按权重排序后批量处理

3. 操作生成策略

// 对于簇内邻域，按深度排序后批量访问
for (auto [x, y, w, id] : ask[i]) {
    if (w < 0) {
        // 特殊情况直接处理
        ans.push_back({1, x, y});
        ans.push_back({3, id, 0});
        ans.push_back({2, 0, 0});
        continue;
    }
    
    // 先移动到簇底端，再移动到目标邻域
    ans.push_back({1, down[x], w});
    ans.push_back({1, x, y});
    ans.push_back({3, id, 0});
    ans.push_back({2, 0, 0});
    t++;
}

// 回溯操作
while (t--) ans.push_back({2, 0, 0});

关键技巧

1. 分块优化

• 簇大小 $B = \sqrt{n}$，平衡操作次数与复杂度
• 利用DFS序连续特性组织簇内节点

2. 邻域排序 按 $dep[x] + y - dep[down[x]]$ 排序，优化移动路径：

• 权重计算：$w = dep[x] + y - dep[down[x]]$
• 保证移动路径单调，减少冗余操作

3. 操作复用

• 通过操作2的回溯机制重用路径
• 批量处理同一簇内的邻域访问请求

复杂度分析

时间复杂度：

• 树分块：$O(n)$
• 邻域排序：$O(m \log m)$
• 总操作数：$O(m)$

空间复杂度：$O(n + m)$

正确性证明

1. 操作合法性：所有操作1满足 $N(x,y) \subseteq N(x',y')$ 的包含关系
2. 覆盖完整性：每个目标邻域恰好被访问一次（操作3）
3. 代价可控：通过分块和路径优化，总代价满足 $2.5\times 10^9$ 限制
4. 操作次数：不超过 $5m$ 次操作

样例验证

输入：

8 4
1 1 1 2 2 2 5
2 1
1 1  
6 0
1 2

输出操作序列合理：

• 操作1在包含关系下移动
• 操作2正确回溯
• 每个目标邻域恰好一次操作3

该算法通过树分块和邻域分类，高效解决了大规模树上有向邻域的遍历问题。