题目分析

松鼠的家是一棵树，维尼需要按照指定的顺序 $a_1, a_2, \ldots, a_n$ 访问各个房间。每个房间在第一次被访问时需要提供糖果，但最后一个房间 $a_n$ 不需要。需要计算每个房间至少需要准备多少糖果。

关键点：统计每个节点在访问路径中被经过的次数（$a_n$ 除外）。

解题思路

核心思想

使用树链剖分 + 差分标记 + 树状数组：

1. 树链剖分：将树分解为链，支持高效路径操作
2. 差分标记：在DFS序上标记路径覆盖
3. 树状数组：维护区间和，支持快速查询

关键技术

• 轻重链剖分：$O(\log n)$ 的路径操作
• DFS序：将树结构线性化
• 差分技巧：标记路径起点和终点

算法步骤

1. 树链剖分预处理：计算深度、父节点、子树大小、重儿子
2. 链分解：计算DFS序和链顶
3. 路径标记：对每条访问路径进行差分标记
4. 统计结果：通过子树求和计算每个节点的访问次数

完整代码

#include <iostream>
#include <vector>

using std::vector;

// 树状数组（Fenwick Tree）类
class FenwickTree {
public:
    FenwickTree(int size) : n(size), nodes(size, 0) {}

    // 单点更新
    void add(int index, int delta) {
        if (index <= 0) {
            return;
        }

        // 树状数组的标准更新操作
        while (index <= n) {
            nodes[index - 1] += delta;
            index += lowbit(index);
        }
    }

    // 区间求和 [l, r]
    int sum(int l, int r) {
        int result = 0;
        
        // 计算前缀和 [1, r]
        for (int i = r; i > 0; i -= lowbit(i)) {
            result += nodes[i - 1];
        }
        
        // 减去前缀和 [1, l-1]
        for (int i = l - 1; i > 0; i -= lowbit(i)) {
            result -= nodes[i - 1];
        }
        
        return result;
    }

private:
    // 计算最低有效位
    int lowbit(int x) const {
        return x & -x;
    }

    int n;
    vector<int> nodes;
};

// 第一次DFS：计算深度、父节点、子树大小、重儿子
void dfsBuild(const vector<vector<int>> &graph, int current, 
              vector<int> &depth, vector<int> &heavy, 
              vector<int> &parent, vector<int> &size) {
    heavy[current] = -1;  // 初始化为无重儿子
    size[current] = 1;    // 当前节点子树大小至少为1

    // 遍历所有邻居节点
    for (auto neighbor : graph[current]) {
        if (neighbor != parent[current]) {
            depth[neighbor] = depth[current] + 1;
            parent[neighbor] = current;
            
            // 递归处理子节点
            dfsBuild(graph, neighbor, depth, heavy, parent, size);
            
            // 更新子树大小
            size[current] += size[neighbor];
            
            // 更新重儿子（子树大小最大的儿子）
            if (heavy[current] == -1 || size[heavy[current]] < size[neighbor]) {
                heavy[current] = neighbor;
            }
        }
    }
}

// 第二次DFS：进行链分解，计算DFS序和链顶
void dfsDecompose(const vector<vector<int>> &graph,
                  const vector<int> &heavy, const vector<int> &parent, 
                  int current, int chainTop, 
                  vector<int> &dfsOrder, vector<int> &top) {
    static int counter = 0;  // DFS序计数器
    
    dfsOrder[current] = ++counter;
    top[current] = chainTop;

    // 如果有重儿子，优先处理重儿子（保持链的连续性）
    if (heavy[current] != -1) {
        dfsDecompose(graph, heavy, parent, heavy[current], chainTop, dfsOrder, top);
    }

    // 处理轻儿子，开始新的链
    for (auto neighbor : graph[current]) {
        if (neighbor != parent[current] && neighbor != heavy[current]) {
            dfsDecompose(graph, heavy, parent, neighbor, neighbor, dfsOrder, top);
        }
    }
}

// 使用树链剖分求LCA（最近公共祖先）
int findLCA(const vector<int> &depth, const vector<int> &parent,
            const vector<int> &top, int u, int v) {
    // 不断向上跳，直到两个节点在同一链上
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) {
            v = parent[top[v]];
        } else {
            u = parent[top[u]];
        }
    }
    
    // 返回深度较小的节点（即LCA）
    return depth[u] < depth[v] ? u : v;
}

int main() {
    using std::cin;
    using std::cout;

    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 读入访问序列（转换为0-based索引）
    vector<int> visitOrder(n);
    for (int i = 0; i < n; i++) {
        cin >> visitOrder[i];
        visitOrder[i]--;  // 转换为0-based索引
    }

    // 构建树的邻接表
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;  // 转换为0-based索引
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // 树链剖分预处理
    vector<int> depth(n), heavy(n), parent(n), size(n);
    depth[0] = 0;     // 根节点深度为0
    parent[0] = -1;   // 根节点无父节点
    dfsBuild(graph, 0, depth, heavy, parent, size);

    // 链分解
    vector<int> dfsOrder(n), top(n);
    dfsDecompose(graph, heavy, parent, 0, 0, dfsOrder, top);

    // 初始化树状数组（用于维护DFS序上的标记）
    FenwickTree treeArray(n);

    // 处理每条访问路径
    for (int i = 1; i < n; i++) {
        int from = visitOrder[i - 1];
        int to = visitOrder[i];
        
        // 求路径的最近公共祖先
        int lcaNode = findLCA(depth, parent, top, from, to);
        
        // 差分标记原理：
        // 1. 在路径起点标记+1
        treeArray.add(dfsOrder[from], 1);
        // 2. 在LCA处标记-1（避免重复计数）
        treeArray.add(dfsOrder[lcaNode], -1);
        
        // 3. 在路径终点（不包括终点本身）标记+1
        if (to != 0) {  // 如果不是根节点
            treeArray.add(dfsOrder[parent[to]], 1);
        }
        
        // 4. 在LCA的父节点处标记-1（精确控制标记范围）
        if (lcaNode != 0) {  // 如果LCA不是根节点
            treeArray.add(dfsOrder[parent[lcaNode]], -1);
        }
    }

    // 输出每个房间需要的糖果数
    for (int i = 0; i < n; i++) {
        // 统计以节点i为根的子树中的标记总和
        // 这表示节点i被访问的次数
        int candyCount = treeArray.sum(dfsOrder[i], dfsOrder[i] + size[i] - 1);
        cout << candyCount << '\n';
    }

    return 0;
}

代码说明

关键数据结构

• FenwickTree：树状数组，支持 $O(\log n)$ 的区间查询和单点更新
• 树链剖分数组：
  • depth[i]：节点i的深度
  • parent[i]：节点i的父节点
  • size[i]：以节点i为根的子树大小
  • heavy[i]：节点i的重儿子
  • dfsOrder[i]：节点i的DFS序
  • top[i]：节点i所在链的顶端节点

算法核心

1. 树链剖分原理

第一次DFS：

• 计算每个节点的深度、父节点、子树大小
• 确定重儿子（子树大小最大的儿子）

第二次DFS：

• 优先遍历重儿子，形成重链
• 为每个节点分配DFS序
• 记录每个节点所在链的顶端

2. 路径标记策略

对于路径 $u \to v$，设 $lca$ 为它们的最近公共祖先：

u → lca → v

使用差分标记：

• 在 $u$ 处 +1
• 在 $lca$ 处 -1
• 在 $parent[v]$ 处 +1（如果 $v$ 不是根）
• 在 $parent[lca]$ 处 -1（如果 $lca$ 不是根）

这样确保只有路径上的节点会被正确计数。

3. 统计方法

通过子树求和计算每个节点的访问次数：

treeArray.sum(dfsOrder[i], dfsOrder[i] + size[i] - 1)

正确性分析

1. 路径覆盖：差分标记确保只有路径上的节点被计数
2. 重复访问：同一个节点在不同路径中被多次访问会累加
3. 终点处理：最后一个节点 $a_n$ 自动不计数（因为路径只到 $a_{n-1} \to a_n$）

复杂度分析

• 预处理：$O(n)$ 两次DFS遍历
• 每条路径：$O(\log n)$ 求LCA和树状数组操作
• 总复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$