5.19

#include <bits/stdc++.h>  
using namespace std;  
  
const int MAXN = 1e5 + 5;  
const int MAXM = 4e6 + 5; // 假设每个节点的值域在 [1, MAXM] 内  
  
int n, m; // n 为序列长度，m 为值域大小（通常为 1e9 但实际存储时可以使用离散化）  
int a[MAXN], rt[MAXN]; // a 为原始序列，rt 存储每棵线段树的根节点  
  
struct Node {  
    int l, r, cnt; // 左子节点，右子节点，该节点表示的值域范围内元素的个数  
} tree[MAXM << 1];  
int tot; // 线段树节点总数  
  
void update(int &p, int l, int r, int x) {  
    if (!p) p = ++tot; // 如果节点为空，新建节点  
    if (l == r) {  
        tree[p].cnt++; // 如果是叶子节点，直接增加计数  
        return;  
    }  
    int mid = (l + r) >> 1;  
    if (x <= mid) update(tree[p].l, l, mid, x);  
    else update(tree[p].r, mid + 1, r, x);  
    tree[p].cnt = tree[tree[p].l].cnt + tree[tree[p].r].cnt; // 更新当前节点计数  
}  
  
int merge(int u, int v, int l, int r) 
{  
    if (!u || !v) return u | v; // 如果其中一个为空，返回另一个  
    if (l == r) {  
        tree[u].cnt += tree[v].cnt; // 如果是叶子节点，直接合并计数  
        return u;  
    }  
    int mid = (l + r) >> 1;  
    tree[u].l = merge(tree[u].l, tree[v].l, l, mid); // 递归合并左子树  
    tree[u].r = merge(tree[u].r, tree[v].r, mid + 1, r); // 递归合并右子树  
    tree[u].cnt = tree[tree[u].l].cnt + tree[tree[u].r].cnt; // 更新当前节点计数  
    return u; // 返回合并后的线段树根节点  
}  
  
// ... 离散化、建树等其他操作 ...  
  
// 假设 dfs 是你的深度优先遍历函数，你可以在这里进行线段树的合并  
void dfs(int u, int fa) 
{  
    // 对于 u 的每个子节点 v  
    for (int v : adj[u]) 
    { // adj[u] 是 u 的邻接表，表示 u 的所有子节点  
        if (v == fa) continue; // 避免重复遍历  
        dfs(v, u); // 先递归遍历子树  
        // 合并 v 的线段树到 u 的线段树上  
        rt[u] = merge(rt[u], rt[v], 1, m); // 假设值域是 1 到 m  
    }  
    // 在这里可以进行其他基于合并后线段树的操作  
}  
  
int main() 
{  
    // ... 读取输入、离散化、建树等操作 ...  
    dfs(1, 0); // 从根节点开始遍历并合并线段树  
    // ... 其他操作 ...  
    return 0;  
}