树链剖分+线段树 HDOJ 5029 Relief grain（分配粮食）

题目链接

题意：

　　分粮食我就当成涂色了。有n个点的一棵树，在a到b的路上都涂上c颜色，颜色可重复叠加，问最后每一个点的最大颜色数量的颜色类型。

思路：

　　首先这题的输出是每一个点最后的情况，考虑离线做法。简化版问题：在一条线段上涂色，问每个点的最后的情况，假设在[a, b]区间涂色，那么在开始的位置a标记开始涂色，在结束的位置标记结束涂色，一棵动态的颜色树，维护当前颜色数量最大的数量。那么这题也可以考虑这么做，先对树进行树链剖分，然后按照剖分顺序dfn来遍历，提前读入所有操作，在涂色的两端标记，后面操作和简化版一样了。

#include <bits/stdc++.h>

const int N = 1e5 + 5;

std::vector<int> edges[N];
int n, m;

//颜色树
#define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1

int mx[N<<2];

void push_up(int o) {
    mx[o] = std::max (mx[o<<1], mx[o<<1|1]);
}

void build(int l, int r, int o) {
    mx[o] = 0;
    if (l == r) return ;
    int mid = l + r >> 1;
    build (lson);
    build (rson);
}

void updata(int p, int c, int l, int r, int o) {
    if (l == r) {
        mx[o] += c;
        return ;
    }
    int mid = l + r >> 1;
    if (p <= mid) updata (p, c, lson);
    else updata (p, c, rson);
    push_up (o);
}

int query(int l, int r, int o) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (mx[o<<1] == mx[o]) return query (lson);
    else return query (rson);
}

int sz[N], fa[N], dfn[N], belong[N];
int idx[N];
int tim;

void DFS2(int u, int chain) {
    dfn[u] = ++tim;
    idx[tim] = u;
    belong[u] = chain;
    int k = 0;
    for (auto v: edges[u]) {
        if (v == fa[u]) continue;
        if (sz[v] > sz[k]) k = v;
    }
    if (k) DFS2 (k, chain);
    for (auto v: edges[u]) {
        if (v == fa[u] || v == k) continue;
        DFS2 (v, v);
    }
}

void DFS(int u, int pa) {
    sz[u] = 1;
    fa[u] = pa;
    for (auto v: edges[u]) {
        if (v == pa) continue;
        DFS (v, u);
        sz[u] += sz[v];
    }
}

std::vector<int> add[N], sub[N];
int ans[N];

void mark(int a, int b, int c) {
    int p = belong[a], q = belong[b];
    while (p != q) {
        if (dfn[p] < dfn[q]) {
            std::swap (p, q);
            std::swap (a, b);
        }
        add[dfn[p]].push_back (c);
        sub[dfn[a]+1].push_back (c);  //son[a]
        a = fa[p];
        p = belong[a];
    }
    if (dfn[a] < dfn[b]) std::swap (a, b);
    add[dfn[b]].push_back (c);
    sub[dfn[a]+1].push_back (c);
}

void prepare() {
    sz[0] = 0;
    DFS (1, 0);
    tim = 0;
    DFS2 (1, 1);
}

int main() {
    while (scanf ("%d%d", &n, &m) == 2 && n + m) {
        for (int i=1; i<=n; ++i) {
            edges[i].clear ();
            add[i].clear ();
            sub[i].clear ();
        }
        for (int i=1; i<n; ++i) {
            int u, v;
            scanf ("%d%d", &u, &v);
            edges[u].push_back (v);
            edges[v].push_back (u);
        }

        prepare ();

        int maxc = 1;
        for (int i=1; i<=m; ++i) {
            int a, b, c;
            scanf ("%d%d%d", &a, &b, &c);
            mark (a, b, c);
            maxc = std::max (maxc, c);
        }
        
        build (1, maxc, 1);

        //dfn
        for (int i=1; i<=n; ++i) {
            for (int j=0; j<add[i].size (); ++j) {
                updata (add[i][j], 1, 1, maxc, 1);
            }
            for (int j=0; j<sub[i].size (); ++j) {
                updata (sub[i][j], -1, 1, maxc, 1);
            }
            ans[idx[i]] = mx[1] ? query (1, maxc, 1) : 0;
        }

        for (int i=1; i<=n; ++i) {
            printf ("%d
", ans[i]);
        }
    }
    return 0;
}