题解：线段树合并解决树上路径统计问题

问题重述

给定一棵n个节点的树，进行m次操作，每次在u到v的路径上所有节点发放一个数字z。最后询问每个节点上出现次数最多的数字（如有多个输出编号最小的）。

算法核心：线段树合并 + 树上差分

1. 树上差分

将路径操作转化为四个点的操作：
• u节点 +1
• v节点 +1
• lca(u,v)节点 -1
• fa[lca(u,v)]节点 -1

2. 线段树合并

• 动态开点权值线段树：每个节点维护一棵线段树，记录数字出现次数
• 合并操作：将子节点的线段树合并到父节点，并维护最大值

关键实现细节

线段树结构设计

struct linetree {
    int s[40*N][2];  // 左右儿子指针（动态开点）
    data v[40*N];     // 节点存储的值（数字和出现次数）
    int ct;           // 节点计数器

    void ins(int p, int l, int r, data va) {
        if(r-l==1) { v[p] = va + v[p]; return; }  // 叶子节点直接合并
        int mid = (l+r)/2;
        if(va.u <= mid) ins(s[p][0] = s[p][0] ? s[p][0] : ++ct, l, mid, va);
        else ins(s[p][1] = s[p][1] ? s[p][1] : ++ct, mid, r, va);
        v[p] = max(v[s[p][0]], v[s[p][1]]);  // 维护区间最大值
    }

    void mg(int p1, int p2, int l, int r) {
        if(r-l==1) { v[p1] = v[p1] + v[p2]; return; }  // 叶子合并
        int mid = (l+r)/2;
        // 处理左子树
        if(s[p1][0] && s[p2][0]) mg(s[p1][0], s[p2][0], l, mid);
        else if(s[p2][0]) s[p1][0] = s[p2][0];  // 直接继承
        // 处理右子树
        if(s[p1][1] && s[p2][1]) mg(s[p1][1], s[p2][1], mid, r);
        else if(s[p2][1]) s[p1][1] = s[p2][1];
        v[p1] = max(v[s[p1][0]], v[s[p1][1]]);  // 更新当前节点
    }
} lt;

树上操作处理

// 树上差分操作
ve[u].push_back({va,1});      // u点+1
ve[v].push_back({va,1});      // v点+1
ve[lc].push_back({va,-1});    // lca点-1
ve[fa[lc][0]].push_back({va,-1}); // lca父节点-1

// 后序遍历合并线段树
void dfs2(int u) {
    for(子节点v : u的孩子) {
        dfs2(v);
        lt.mg(u, v, 0, 1e5);  // 合并子树线段树
    }
    for(auto it : ve[u]) {
        lt.ins(u, 0, 1e5, it); // 处理当前节点操作
    }
    ans[u] = lt.v[u].u;  // 记录答案
}

复杂度分析

• 时间：O((n+m) log C)，其中C是数字值域（1e5）
• 空间：O(n log C)，动态开点线段树

思考过程

1. 暴力思路：直接遍历每个路径修改，O(nm)超时
2. 优化方向：
   • 树上差分减少操作次数
   • 线段树高效维护动态统计
3. 数据结构选择：
   • 权值线段树处理数字统计
   • 动态开点节省空间
4. 合并策略：
   • 子树合并时共用节点
   • 懒惰更新减少操作

样例解释

输入：

5 3
1 2
3 1
3 4
5 3
2 3 3
1 5 2
3 3 3

处理：
1. 路径2-3发放3：2(+1),3(+1),1(-1),0(-1)
2. 路径1-5发放2：1(+1),5(+1),3(-1),1(-1)
3. 路径3-3发放3：3(+1),3(+1),3(-1),1(-1)

最终各节点最多数字：
• 节点1：2（出现1次）
• 节点2：3（1次）
• 节点3：3（2次）
• 节点4：无
• 节点5：2（1次）

总结

本题展示了如何用线段树合并高效解决树上路径统计问题。关键在于：
1. 将路径操作转化为点操作（差分）
2. 用动态开点线段树维护值域信息
3. 通过合并子树信息自底向上计算

这种树上统计+值域维护的思路，适用于许多树形结构上的统计问题。