353 雨天的尾巴

发表于 分类于 阅读次数： Waline： 本文字数： 950 阅读时长 ≈ 3 分钟

考点

  • 树上差分
  • 线段树合并
  • LCA

题解

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int n, m, d[maxn], f[maxn][18];
queue<int> q;
// 离散化
int cnt, dis[maxn];
struct {
  int x, y, z;
} req[maxn];
int tot, head[maxn], nxt[maxn * 2], ver[maxn * 2];
// 线段树，保存区间最大值和最大值的位置
int num, rt[maxn];
int lc[maxn * 4 * 18], rc[maxn * 4 * 18], mx[maxn * 4 * 18], pos[maxn * 4 * 18];

void add(int x, int y) { ver[++tot] = y, nxt[tot] = head[x], head[x] = tot; }

int lca(int x, int y) {
  if (d[x] < d[y]) swap(x, y);
  for (int i = 17; i >= 0; i--) {
    if (d[f[x][i]] >= d[y]) x = f[x][i];
  }
  if (x == y) return x;
  for (int i = 17; i >= 0; --i) {
    if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
  }
  return f[x][0];
}

void bfs() {
  q.push(1), d[1] = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = nxt[i]) {
      int y = ver[i];
      if (d[y]) continue;
      q.push(y);
      d[y] = d[x] + 1;
      f[y][0] = x;
      for (int j = 1; j <= 17; ++j) {
        f[y][j] = f[f[y][j - 1]][j - 1];
      }
    }
  }
}

void up(int p) {
  mx[p] = max(mx[lc[p]], mx[rc[p]]);
  pos[p] = mx[lc[p]] >= mx[rc[p]] ? pos[lc[p]] : pos[rc[p]];
}

void update(int &p, int l, int r, int x, int v) {
  if (!p) p = ++cnt;
  if (l == r) {
    mx[p] += v;
    pos[p] = mx[p] ? x : 0;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(lc[p], l, mid, x, v);
  else
    update(rc[p], mid + 1, r, x, v);
  up(p);
}

int merge(int p, int q, int l, int r) {
  if (!p || !q) return p + q;
  if (l == r) {
    mx[p] += mx[q];
    pos[p] = mx[p] ? l : 0;
    return p;
  }
  int mid = (l + r) >> 1;
  lc[p] = merge(lc[p], lc[q], l, mid);
  rc[p] = merge(rc[p], rc[q], mid + 1, r);
  up(p);
  return p;
}

void dfs(int x) {
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (d[x] >= d[y]) continue;
    dfs(y);
    rt[x] = merge(rt[x], rt[y], 1, num);
  }
}

int main() {
  int x, y, z;
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &x, &y);
    add(x, y), add(y, x);
  }
  bfs();
  // 每个节点新建一个子树
  for (int i = 1; i <= n; ++i) rt[i] = ++cnt;
  // 离散化
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &x, &y, &z);
    req[i].x = x, req[i].y = y, req[i].z = z;
    dis[++num] = z;
  }
  sort(dis + 1, dis + 1 + num);
  num = unique(dis + 1, dis + 1 + num) - 1 - dis;
  // 修改节点线段树
  for (int x, y, z, i = 1; i <= m; ++i) {
    x = req[i].x, y = req[i].y;
    z = lower_bound(dis + 1, dis + 1 + num, req[i].z) - dis;
    int u = lca(x, y);
    update(rt[x], 1, num, z, 1);
    update(rt[u], 1, num, z, -1);
    update(rt[y], 1, num, z, 1);
    if (u != 1) update(rt[f[u][0]], 1, num, z, -1);
  }
  // 子树合并
  dfs(1);
  for (int i = 1; i <= n; ++i) printf("%d\n", dis[pos[rt[i]]]);
  return 0;
}

思路

先将所有请求离线保存后，对z进行离散化，得到num个排名。

那么树的每个节点都是一个长度为num的计数数组，记录不同物品的个数，

那么最坏情况下空间开销就是n * m -> 1e5 * 1e5 -> 1e10，时间复杂度也是如此，双炸。

考虑树上差分，每个节点的数组换成长度为num的差分数组，记录每个物品的变化量，整棵树求和一次就能得到最终的值；但数组每次合并还是需要num的时间复杂度，整棵树也是n * num量级的。

所以将每个节点开一颗权值线段树，叶子节点下标代表物品种类，值代表不同物品的变化量之和，

操作则是记录区间最大值至mx，记录最大值的下标至pos；

两个节点合并，那么也就是两颗权值线段树合并，叶子节点的值相加，就满足了子树求和这一操作；

加上线段树的区间最大值操作，很容易维护答案。

这里作图描述一下树上差分，假设有(x, y, z)：

1
2
3
4
5
int u = lca(x, y);
update(rt[x], 1, num, z, 1);
update(rt[u], 1, num, z, -1);
update(rt[y], 1, num, z, 1);
if (u != 1) update(rt[f[u][0]], 1, num, z, -1);