// 重链剖分实现
#include <iostream>
#include <vector>
using namespace std;

class HeavyLightDecomposition {
private:
    int n, timer;
    vector<vector<int>> adj;
    vector<int> parent, depth, heavy, head, pos, subtreeSize;
    
    // 第一次DFS：计算子树大小和重儿子
    void dfs1(int v, int p, int d) {
        parent[v] = p;
        depth[v] = d;
        subtreeSize[v] = 1;
        
        int maxSize = 0;
        for (int u : adj[v]) {
            if (u != p) {
                dfs1(u, v, d + 1);
                subtreeSize[v] += subtreeSize[u];
                if (subtreeSize[u] > maxSize) {
                    maxSize = subtreeSize[u];
                    heavy[v] = u;
                }
            }
        }
    }
    
    // 第二次DFS：分配链头和位置
    void dfs2(int v, int h) {
        head[v] = h;
        pos[v] = timer++;
        
        // 优先遍历重儿子
        if (heavy[v] != -1) {
            dfs2(heavy[v], h);
        }
        
        // 遍历轻儿子，每个轻儿子开始新链
        for (int u : adj[v]) {
            if (u != parent[v] && u != heavy[v]) {
                dfs2(u, u);
            }
        }
    }
    
public:
    HeavyLightDecomposition(int size) : n(size), timer(0) {
        adj.resize(n);
        parent.resize(n);
        depth.resize(n);
        heavy.assign(n, -1);
        head.resize(n);
        pos.resize(n);
        subtreeSize.resize(n);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void build(int root = 0) {
        dfs1(root, -1, 0);
        dfs2(root, root);
    }
    
    // 查询路径上的所有区间
    vector<pair<int, int>> getPathIntervals(int u, int v) {
        vector<pair<int, int>> result;
        
        while (head[u] != head[v]) {
            if (depth[head[u]] > depth[head[v]]) {
                result.push_back({pos[head[u]], pos[u]});
                u = parent[head[u]];
            } else {
                result.push_back({pos[head[v]], pos[v]});
                v = parent[head[v]];
            }
        }
        
        // 处理同一条链上的部分
        if (pos[u] > pos[v]) swap(u, v);
        result.push_back({pos[u], pos[v]});
        
        return result;
    }
    
    // 查询LCA
    int lca(int u, int v) {
        while (head[u] != head[v]) {
            if (depth[head[u]] > depth[head[v]]) {
                u = parent[head[u]];
            } else {
                v = parent[head[v]];
            }
        }
        return depth[u] < depth[v] ? u : v;
    }
    
    // 获取子树区间
    pair<int, int> getSubtreeInterval(int v) {
        return {pos[v], pos[v] + subtreeSize[v] - 1};
    }
    
    // 获取节点在序列中的位置
    int getPosition(int v) {
        return pos[v];
    }
    
    // 获取节点深度
    int getDepth(int v) {
        return depth[v];
    }
};

// 配合线段树的路径查询
class SegmentTree {
private:
    vector<long long> tree, lazy;
    int n;
    
    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }
    
    void updateRange(int node, int start, int end, int l, int r, long long val) {
        push(node, start, end);
        if (start > r || end < l) return;
        
        if (start >= l && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
        
        int mid = (start + end) / 2;
        updateRange(2 * node, start, mid, l, r, val);
        updateRange(2 * node + 1, mid + 1, end, l, r, val);
        
        push(2 * node, start, mid);
        push(2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    long long queryRange(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        
        push(node, start, end);
        if (start >= l && end <= r) return tree[node];
        
        int mid = (start + end) / 2;
        return queryRange(2 * node, start, mid, l, r) + 
               queryRange(2 * node + 1, mid + 1, end, l, r);
    }
    
public:
    SegmentTree(int size) : n(size) {
        tree.resize(4 * n);
        lazy.resize(4 * n);
    }
    
    void update(int l, int r, long long val) {
        updateRange(1, 0, n - 1, l, r, val);
    }
    
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};

// 树上路径操作
class TreePathOperations {
private:
    HeavyLightDecomposition hld;
    SegmentTree seg;
    
public:
    TreePathOperations(int n) : hld(n), seg(n) {}
    
    void addEdge(int u, int v) {
        hld.addEdge(u, v);
    }
    
    void build(int root = 0) {
        hld.build(root);
    }
    
    // 路径更新
    void updatePath(int u, int v, long long val) {
        vector<pair<int, int>> intervals = hld.getPathIntervals(u, v);
        for (auto [l, r] : intervals) {
            seg.update(l, r, val);
        }
    }
    
    // 路径查询
    long long queryPath(int u, int v) {
        long long result = 0;
        vector<pair<int, int>> intervals = hld.getPathIntervals(u, v);
        for (auto [l, r] : intervals) {
            result += seg.query(l, r);
        }
        return result;
    }
    
    // 子树更新
    void updateSubtree(int v, long long val) {
        auto [l, r] = hld.getSubtreeInterval(v);
        seg.update(l, r, val);
    }
    
    // 子树查询
    long long querySubtree(int v) {
        auto [l, r] = hld.getSubtreeInterval(v);
        return seg.query(l, r);
    }
    
    // LCA查询
    int lca(int u, int v) {
        return hld.lca(u, v);
    }
};

int main() {
    // 构建测试树
    TreePathOperations tpo(7);
    
    // 添加边
    tpo.addEdge(0, 1);
    tpo.addEdge(0, 2);
    tpo.addEdge(1, 3);
    tpo.addEdge(1, 4);
    tpo.addEdge(2, 5);
    tpo.addEdge(2, 6);
    
    tpo.build(0);
    
    // 路径更新
    tpo.updatePath(3, 5, 10);
    cout << "路径3到5的和： " 
         << tpo.queryPath(3, 5) << endl;
    
    // 子树操作
    tpo.updateSubtree(1, 5);
    cout << "子树1的和： " 
         << tpo.querySubtree(1) << endl;
    
    // LCA查询
    cout << "节点4和6的LCA： " 
         << tpo.lca(4, 6) << endl;
    
    return 0;
}