P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 （树上差分+线段树合并）

显然的树上差分问题，最后要我们求每个点数量最多的物品，考虑对每个点建议线段树，查询子树时将线段树合并可以得到答案。

用动态开点的方式建立线段树，注意离散化。

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 const int N = 1e5 + 10;

  4 struct node {

  5     int lc, rc, dat, pos;//dat记录最多的物品的次数，pos记录位置

  6 }tr[N * 20 * 4];

  7 int head[N], to[N << 1], nxt[N << 1], tot;

  8 int n, m, num, cnt, t, ans[N];

  9 int d[N], st[N][20], rt[N], X[N], Y[N], Z[N], val[N];

 10 inline int read() {

 11     int x = 0,f = 1;char ch = getchar();

 12     while (ch<'0' || ch>'9') { if(ch == '-') f = -1;ch = getchar(); }

 13     while (ch >= '0'&&ch <= '9') x = x * 10 + ch - '0',ch = getchar();

 14     return x * f;

 15 }

 16 void add(int x, int y) {

 17     nxt[++tot] = head[x];

 18     head[x] = tot;

 19     to[tot] = y;

 20 }

 21

 22 void dfs(int u, int f) {

 23      for (int i = head[u]; i; i = nxt[i]) {

 24          int v = to[i];

 25          if (d[v]) continue;

 26          d[v] = d[u] + 1;

 27          st[v][0] = u;

 28          for (int j = 1; j <= t; j++)

 29              st[v][j] = st[st[v][j-1]][j-1];

 30          dfs(v, u);

 31      }

 32 }

 33

 34 int lca(int x, int y) {

 35     if (d[x] > d[y]) swap(x, y);

 36     for (int i = t; i >= 0; i--)

 37         if (d[st[y][i]] >= d[x]) y = st[y][i];

 38     if (x == y) return x;

 39     for (int i = t; i >= 0; i--)

 40         if (st[x][i] != st[y][i]) x = st[x][i], y = st[y][i];

 41     return st[x][0];

 42 }

 43

 44 void insert(int p, int l, int r, int val, int k) {

 45     if (l == r) {

 46         tr[p].dat += k;

 47         tr[p].pos = tr[p].dat ? l : 0;

 48         return ;

 49     }

 50     int mid = (l + r) >> 1;

 51     if(val <= mid) {

 52         if (!tr[p].lc)    tr[p].lc = ++num;//动态开点

 53         insert(tr[p].lc, l, mid, val, k);

 54     }

 55     else {

 56         if (!tr[p].rc) tr[p].rc = ++num;

 57         insert(tr[p].rc, mid + 1, r, val, k);

 58     }

 59     tr[p].dat = max(tr[tr[p].lc].dat, tr[tr[p].rc].dat);

 60     tr[p].pos = tr[tr[p].lc].dat >= tr[tr[p].rc].dat ? tr[tr[p].lc].pos : tr[tr[p].rc].pos;

 61 }

 62

 63 int merge(int p, int q, int l, int r) {//线段树合并

 64     if (!p || !q) return p + q;

 65     if (l == r) {

 66         tr[p].dat += tr[q].dat;

 67         tr[p].pos = tr[p].dat ? l : 0;

 68         return p;

 69     }

 70     int mid = (l + r) >> 1;

 71     tr[p].lc = merge(tr[p].lc, tr[q].lc, l, mid);

 72     tr[p].rc = merge(tr[p].rc, tr[q].rc, mid + 1, r);

 73     tr[p].dat = max(tr[tr[p].lc].dat, tr[tr[p].rc].dat);

 74     tr[p].pos = tr[tr[p].lc].dat >= tr[tr[p].rc].dat ? tr[tr[p].lc].pos : tr[tr[p].rc].pos;

 75     return p;

 76 }

 77

 78 void solve(int x) {

 79     for (int i = head[x]; i; i = nxt[i]) {

 80         int y = to[i];

 81         if (d[y] <= d[x]) continue;

 82         solve(y);

 83         rt[x] = merge(rt[x], rt[y], 1, cnt);

 84     }

 85     ans[x] = tr[rt[x]].pos;

 86 }

 87

 88 int main() {

 89     n = read(); m = read();

 90     t = log2(n) + 1;

 91     for (int i = 1; i < n; i++) {

 92         int x = read(), y = read();

 93         add(x, y), add(y, x);

 94     }

 95     d[1] = 1, dfs(1,0);

 96     for (int i = 1; i <= n; i++) rt[i] = ++num;

 97     for (int i = 1; i <= m; i++) {

 98         X[i] = read(); Y[i] = read(); Z[i] = read();

 99         val[i] = Z[i];

100     }

101     sort(val + 1, val + m + 1);//离散化

102     cnt = unique(val + 1, val + m + 1) - val - 1;

103     for (int i = 1; i <= m; i++) {

104         int x = X[i], y = Y[i];

105         int z = lower_bound(val + 1, val + cnt + 1, Z[i]) - val;

106         int p = lca(x, y);

107         //树上差分

108         insert(rt[x], 1, cnt, z, 1);

109         insert(rt[y], 1, cnt, z, 1);

110         insert(rt[p], 1, cnt, z, -1);

111         if (st[p][0]) insert(rt[st[p][0]], 1, cnt, z, -1);

112     }

113     solve(1);

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

115     return 0;

116 }

P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并 （树上差分+线段树合并）的相关教程结束。