您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 3307 雨天的尾巴：樹上路徑顏色統計 + 線段樹合併 (DSU on Tree)

編輯：關於C++

題目大意

給定一棵 n 個節點的樹，m 次操作。每次操作給定路徑 (x, y) 和顏色 z，將路徑上所有節點的顏色 z 計數 +1。所有操作結束後，輸出每個節點計數最多的顏色 (若有多個輸出任意)。

約束：n, m ≤ 10⁵，顏色值 ≤ 10⁹。

核心技術：差分 + DSU on Tree (線段樹合併)

1. 樹上路徑差分

對路徑 (x, y) 加顏色 z，等價於：

x 標記 +z
y 標記 +z
LCA(x,y) 標記 -z
parent[LCA(x,y)] 標記 -z (若存在)

然後 DFS 一次，子樹信息向上合併，每個節點彙總的標記即為其最終顏色計數。這是標準的「樹上差分」技巧。

2. 線段樹維護顏色計數

顏色值範圍大 (10⁹)，需動態開點線段樹 (權值線段樹)。每個節點維護：

val：該區間最大計數
pos：取得最大計數的顏色值 (任意一個)

支持操作：

Modify(pos, delta)：單點加 delta (+1 或 -1)
Merge(other)：合併另一棵線段樹 (DSU on Tree 核心)
QueryMax()：返回 (val, pos)

3. DSU on Tree (小合大優化)

DFS 遍歷樹：

對每個子節點遞歸，得到其線段樹
將子線段樹 合併到當前節點 (小合大：將較小的樹合併到較大的，保證每個節點被合併 O(log n) 次)
處理當前節點的差分標記 (Modify)
查詢最大值作為答案

完整代碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100100;
const int INF_COLOR = 1e9;

struct SegNode {
    SegNode *ls, *rs;
    int val, pos;
    SegNode() : ls(nullptr), rs(nullptr), val(0), pos(0) {}
    
    void pushUp() {
        val = 0; pos = 0;
        if (ls && ls->val > val) { val = ls->val; pos = ls->pos; }
        if (rs && rs->val > val) { val = rs->val; pos = rs->pos; }
    }
};

// 內存池分配
SegNode pool[MAXN * 40];
int poolPtr = 0;
SegNode* newNode() {
    SegNode* p = &pool[poolPtr++];
    p->ls = p->rs = nullptr;
    p->val = 0; p->pos = 0;
    return p;
}

void modify(SegNode*& p, int l, int r, int pos, int delta) {
    if (!p) p = newNode();
    if (l == r) {
        p->val += delta;
        p->pos = l;
        if (p->val == 0) p = nullptr; // 可選：刪除零節點
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) modify(p->ls, l, mid, pos, delta);
    else modify(p->rs, mid+1, r, pos, delta);
    p->pushUp();
    if (p->val == 0) p = nullptr;
}

void merge(SegNode*& a, SegNode* b, int l, int r) {
    if (!b) return;
    if (!a) { a = b; return; }
    if (l == r) {
        a->val += b->val;
        return;
    }
    int mid = (l + r) >> 1;
    merge(a->ls, b->ls, l, mid);
    merge(a->rs, b->rs, mid+1, r);
    a->pushUp();
}

vector tree[MAXN];
vector> ops[MAXN]; // (color, delta)
int ans[MAXN];
int dep[MAXN], fa[MAXN][17];
int n, m;

void dfsLCA(int u, int p) {
    fa[u][0] = p;
    dep[u] = dep[p] + 1;
    for (int i = 1; i < 17; ++i) fa[u][i] = fa[fa[u][i-1]][i-1];
    for (int v : tree[u]) if (v != p) dfsLCA(v, u);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 16; i >= 0; --i) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    if (u == v) return u;
    for (int i = 16; i >= 0; --i) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

SegNode* seg[MAXN];

void dfsSolve(int u, int p) {
    for (int v : tree[u]) if (v != p) {
        dfsSolve(v, u);
        merge(seg[u], seg[v], 1, INF_COLOR);
    }
    for (auto [col, delta] : ops[u]) {
        modify(seg[u], 1, INF_COLOR, col, delta);
    }
    if (seg[u]) ans[u] = seg[u]->pos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfsLCA(1, 0);
    for (int i = 0; i < m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        int l = lca(x, y);
        ops[x].emplace_back(z, 1);
        ops[y].emplace_back(z, 1);
        ops[l].emplace_back(z, -1);
        if (fa[l][0]) ops[fa[l][0]].emplace_back(z, -1);
    }
    dfsSolve(1, 0);
    for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
    return 0;
}