「洛谷 P4556」雨天的尾巴 - 线段树合并 + 最近公共祖先 + 树上差分

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

首先村落里的一共有 \(n\) 座房屋，并形成一个树状结构。然后救济粮分 \(m\) 次发放，每次选择两个房屋 \((x,~y)\)，然后对于 \(x\) 到 \(y\) 的路径上(含 \(x\) 和 \(y\))每座房子里发放一袋 \(z\) 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

对于 \(100\%\) 测试数据，保证 \(1 \leq n, m \leq 10^5\)，\(1 \leq a,b,x,y \leq n\)，\(1 \leq z \leq 10^5\)。

解题思路

由于村落是树状结构，对于从 \(x\) 到 \(y\) 的路径我们可以用 LCA 求出。但直接使用 LCA 后修改则复杂度过高，于是我们可以考虑使用树上差分。假设 \(x\) 与 \(y\) 的 LCA 为 \(f\)，我们可以将 \(x\)，\(y\) 的救济粮 \(+1\)，将 \(f\) 与 \(f\) 的父节点的救济粮 \(-1\)，最后求的时候从叶子节点向根节点作差分的前缀和即可得出每个节点的救济粮个数。

对于每种救济粮的最大值，我们可以在每个节点开一颗权值线段树维护。树上差分则在线段树上修改，然后在求前缀和的时候使用线段树合并即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <cstdio>
#include <iostream>
#include <vector>

const int MAXN = 1e5;
const int LOG_MAXN = 17;

struct Food {
    int cnt, type;

    Food() {}
    Food(int cnt, int type) : cnt(cnt), type(type) {}

    bool operator>(const Food &other) {
        if (cnt == other.cnt) return type < other.type;
        return cnt > other.cnt;
    }
};

struct SegT {
    int l, r;
    SegT *lc, *rc;
    Food val;

    SegT(int l, int r, SegT *lc, SegT *rc) : l(l), r(r), lc(lc), rc(rc), val(Food(0, 0)) {}
    SegT(int l, int r, SegT *lc, SegT *rc, Food val) : l(l), r(r), lc(lc), rc(rc), val(val) {}

    static SegT *build(const int l, const int r) {
        if (l > r) return NULL;
        else if (l == r) return new SegT(l, r, NULL, NULL, Food(0, l));
        else return new SegT(l, r, NULL, NULL);
    }

    void update(const int pos, const long long delta) {
        if (pos > this->r || pos < this->l) return;
        else if (pos == this->l && pos == this->r) val.cnt += delta;
        else {
            int mid = l + (r - l) / 2;
            if (pos <= mid) {
                if (!lc) lc = build(l, mid);
                lc->update(pos, delta);
            } else {
                if (!rc) rc = build(mid + 1, r);
                rc->update(pos, delta);
            }
            Food res(0, 0);
            if (lc && lc->val > res) res = lc->val;
            if (rc && rc->val > res) res = rc->val;
            val = res;
        }
    }

    static SegT *merge(SegT *u, SegT *v) {
        if (!u) return v;
        if (!v) return u;
        if (u->l == u->r) {
            u->val.cnt = u->val.cnt + v->val.cnt;
            return u;
        }

        u->lc = merge(u->lc, v->lc);
        u->rc = merge(u->rc, v->rc);
        Food res(0, 0);
        if (u->lc && u->lc->val > res) res = u->lc->val;
        if (u->rc && u->rc->val > res) res = u->rc->val;
        u->val = res;

        return u;
    }
};

struct Node {
    std::vector<struct Edge> e;
    int d, ans;
    Node *p, *f[LOG_MAXN + 1];
    SegT *segment;
} N[MAXN + 1];

struct Edge {
    Node *s, *t;

    Edge(Node *s, Node *t) : s(s), t(t) {}
};

int n, m;
int ans[MAXN + 1];

inline void addEdge(int s, int t) {
    N[s].e.push_back(Edge(&N[s], &N[t]));
    N[t].e.push_back(Edge(&N[t], &N[s]));
}

void prepare(Node *v, Node *f = NULL) {
    v->f[0] = v->p = f;
    v->d = (f ? f->d : 0) + 1;
    for (int i = 1; i <= LOG_MAXN; i++) {
        if (v->f[i - 1]) {
            v->f[i] = v->f[i - 1]->f[i - 1];
        }
    }
    for (Edge *e = &v->e.front(); e && e <= &v->e.back(); e++) {
        if (e->t == f) continue;
        prepare(e->t, v);
    }
}

inline Node *lca(Node *u, Node *v) {
    if (u->d < v->d) std::swap(u, v);
    if (u->d != v->d) {
        for (int i = LOG_MAXN; i >= 0; i--) {
            if (u->f[i] && u->f[i]->d >= v->d) {
                u = u->f[i];
            }
        }
    }
    if (u != v) {
        for (int i = LOG_MAXN; i >= 0; i--) {
            if (u->f[i] != v->f[i]) {
                u = u->f[i];
                v = v->f[i];
            }
        }
        return u->p;
    }
    return u;
}

void dfs(Node *v, Node *f = NULL) {
    for (Edge *e = &v->e.front(); e && e <= &v->e.back(); e++) {
        if (e->t == f) continue;
        dfs(e->t, v);
    }
    v->ans = v->segment->val.type;
    if (f) f->segment = SegT::merge(f->segment, v->segment);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        addEdge(a, b);
    }

    for (int i = 1; i <= n; i++) N[i].segment = SegT::build(1, MAXN);
    prepare(&N[1]);
    while (m--) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        Node *u = &N[x], *v = &N[y];
        Node *f = lca(u, v);
        u->segment->update(z, 1);
        v->segment->update(z, 1);
        f->segment->update(z, -1);
        if (f->p) f->p->segment->update(z, -1);
    }

    dfs(&N[1]);

    for (int i = 1; i <= n; i++) printf("%d\n", N[i].ans);

    return 0;
}