HDU 5029 Relief grain 树链剖分 好题

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5029

题意：给定一棵树，有n个点，有m次操作，先有n - 1行形式如 a b，代表a b之间有边，然后是m行形式如a b c，代表将从点a到点b路径上的点都给予一种粮食c。最后输出每个点的个数最多的粮食类型。

思路：很容易想到树链剖分，但是粮食种类达100000，怎么用线段树维护每个点的粮食种类及其数量是个难题，肯定不能为每个点开一个数组去维护。我们可以换一种方式，用线段树去维护粮食，每个点代表一种粮食，区间[l, r]维护的是区间内某种粮食的最大值。对于m次操作，先把操作处理成线性的，然后对于区间[l, r]加c，可以在l处标记1，代表此点（这个点不是线段树上的点，而是题中所给树的点）c粮食数量+1， r + 1处标记-1，代表此点c粮食数量-1，这是因为我们按题目中给定的树中的点去更新线段树，走到某个点时，线段树中维护的就是当前这个点的粮食色种类和数量，当更新到区间[l, r]外时，要把对应的c减去1。然后线段树根节点中保存的就是某点的某种粮食的最大数量和其种类，对应输出即可

总结：真是好题啊。。。期间一直莫名MLE，一脸懵逼，后来我重写了dfs1和dfs2，就A了，仔细对比重写之前和之后的代码，并没有什么不一样啊。。。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100010;
typedef pair<int, int> P;
struct edge
{
    int to, next;
}g[N*2];
struct node
{
    int l, r, maxx, id;
}s[N*4];
int head[N], top[N], siz[N], son[N], dep[N], id[N], fat[N], ans[N];
int n, m, cnt, num;
vector<P> arr[N];
void add_edge(int v, int u)
{
    g[cnt].to = u;
    g[cnt].next = head[v];
    head[v] = cnt++;
}
void dfs1(int v, int d, int fa)
{
    dep[v] = d, siz[v] = 1, son[v] = 0, fat[v] = fa;
    for(int i = head[v]; i != -1; i = g[i].next)
    {
        int u = g[i].to;
        if(u != fa)
        {
            dfs1(u, d + 1, v);
            siz[v] += siz[u];
            if(siz[son[v]] < siz[u]) son[v] = u;
        }
    }
}
void dfs2(int v, int tp)
{
    top[v] = tp, id[v] = ++num;
    if(son[v]) dfs2(son[v], tp);
    for(int i = head[v]; i != -1; i = g[i].next)
    {
        int u = g[i].to;
        if(u != fat[v] && u != son[v]) dfs2(u, u);
    }
}
void renew(int v, int u, int c)
{
    int t1 = top[v], t2 = top[u];
    while(t1 != t2)
    {
        if(dep[t1] < dep[t2])
            swap(t1, t2), swap(v, u);
        arr[id[t1]].push_back(P(c, 1));
        arr[id[v]+1].push_back(P(c, -1));
        v = fat[t1], t1 = top[v];
    }
    if(dep[v] > dep[u]) swap(v, u);
    arr[id[v]].push_back(P(c, 1));
    arr[id[u]+1].push_back(P(c, -1));
}
void build(int l, int r, int k)
{
    s[k].l = l, s[k].r = r, s[k].maxx = 0, s[k].id = l;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, k << 1);
    build(mid + 1, r, k << 1|1);
}
void push_up(int k)
{
    if(s[k<<1].maxx < s[k<<1|1].maxx)
        s[k].maxx = s[k<<1|1].maxx, s[k].id = s[k<<1|1].id;
    else
        s[k].maxx = s[k<<1].maxx, s[k].id = s[k<<1].id;
}
void update(int x, int c, int k)
{
    if(s[k].l == s[k].r)
    {
        s[k].maxx += c;
        return;
    }
    int mid = (s[k].l + s[k].r) >> 1;
    if(x <= mid) update(x, c, k << 1);
    else update(x, c, k << 1|1);
    push_up(k);
}
int main ()
{
    int a, b, c;
    while(scanf("%d%d", &n, &m), n || m)
    {
        cnt = num = 0;
        memset(head, -1, sizeof head);
        for(int i = 1; i <= n - 1; i++)
        {
            scanf("%d%d", &a, &b);
            add_edge(a, b);
            add_edge(b, a);
        }
        dfs1(1, 1, 0);
        dfs2(1, 1);
        int tmp = 1;
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            renew(a, b, c);
            tmp = max(tmp, c);
        }
        build(1, tmp, 1);
        for(int i = 1; i <= n; i++)
        {
            int len = arr[i].size();
            for(int j = 0; j < len; j++)
                update(arr[i][j].first, arr[i][j].second, 1);
            if(s[1].maxx == 0) ans[i] = 0;
            else ans[i] = s[1].id;
        }
        for(int i = 1; i <= n; i++)
            printf("%d\n", ans[id[i]]);
        for(int i = 1; i <= num + 1; i++)
            arr[i].clear();
    }

    return 0;
}