354. 天天爱跑步

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 树上差分
  • 时间戳

题解

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 50, lg = (int)(log2(maxn)) + 1;
int n, m;
queue<int> q;
int tot, head[maxn], nxt[maxn << 1], ver[maxn << 1];
int d[maxn], w[maxn], ans[maxn], f[maxn][lg];
// 两个方向的差分数组
// 第一维，左向上方向；第二维右向上方向
int c[maxn << 1][2];
// 得用vector，时间换空间，邻接表会炸
struct node {
  int idx, value, kind;
};
vector<node> a[maxn];

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

void add_q(int x, int i, int v, int k) { a[x].push_back({i, v, k}); }

void bfs() {
  d[1] = 1, q.push(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;
      d[y] = d[x] + 1;
      q.push(y);
      f[y][0] = x;
      for (int j = 1; j < lg; ++j) f[y][j] = f[f[y][j - 1]][j - 1];
    }
  }
}

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

void dfs(int x, int f) {
  int v0 = c[w[x] + d[x]][0], v1 = c[w[x] - d[x] + n][1];
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (y == f) continue;
    dfs(y, x);
  }
  for (auto it : a[x]) {
    int i = it.idx, v = it.value, k = it.kind;
    c[i][k] += v;
  }

  ans[x] = c[w[x] + d[x]][0] - v0 + c[w[x] - d[x] + n][1] - v1;
}

int main() {
  scanf("%d%d", &n, &m);
  int x, y, s, t;
  for (int i = 1; i < n; ++i) {
    scanf("%d%d", &x, &y);
    add(x, y), add(y, x);
  }
  for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
  bfs();
  while (m--) {
    scanf("%d%d", &s, &t);
    int u = lca(s, t);
    add_q(s, d[s], 1, 0);
    if (f[u][0]) add_q(f[u][0], d[s], -1, 0);
    // +n是为了防止负数
    add_q(t, d[s] - 2 * d[u] + n, 1, 1);
    add_q(u, d[s] - 2 * d[u] + n, -1, 1);
  }
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  return 0;
}

思路

设u = lca(s, t)，一条路径可以被u分成两半，假设左半部分为s到含u这部分，右半部分为不含u到t这部分。

对于左半部分的点x，s如果在第w[x]到达，满足d[s] = d[x] + w[x]；

对于右半部分的点x，s如果在第w[x]到达，满足d[s] - 2 * d[u] = w[x] - d[x]。

所以得到，每个点的答案 = 所有路径的左半部分对x的贡献 + 所有路径的右半部分对x的贡献

暴力的解决方案是每个点都开一个二维计数数组，即c[maxn << 1][2]，

第一维记录左半部分的贡献，第二维记录右半部分的贡献。

对于路径左半部分的点，即s ~ u，全部在c[d[s]][0]下标自增即可；

原因在于，每个点的左贡献是通过访问d[x] + w[x]下标，如果d[x] + w[x] == 某个d[s]，那么该路径就会对本x有贡献；

同理，对于路径右半部分的点，即u(不含) ~ t，全部在c[d[s] - 2 * d[u] + n][1]下标自增即可；

（+n是为了防止负数下标导致越界）

原因在于，每个点的右贡献是通过访问w[x] - d[x]下标，如果w[x] - d[x] == 某个d[s] - 2 * d[u]，那么该路径就会对本x有贡献。

整理一下，需要区间增减全部结束之后，再根据值域访问计数，很容易想到权值线段树，也就是树上差分+线段树合并这样的方案。

但本题空间只有128MB，按照线段树动态开点的特性，估算一下空间开销：

树上差分每次需要更新2个点

mlogn的空间复杂度

3个数组，左孩子右孩子与区间计数和

int类型4个字节

总共2 × 3e5 × log2(3e5) × 3 × 4 / 1024 / 1024 = 137MB，直接爆了

根据DFS序，仔细思考这点：

  • 所有的树上差分结束之后，结点本身与其所有子树的差分数组合并就得到了该结点的最终差分情况

  • 每个点只关心d[x] + w[x]和w[x] - d[x]这俩下标的个数，不需要区间操作

那么我们完全可以这么做：

  • c[maxn << 1][2]数组作为全局差分数组，效果不变。

  • 进入点x之前，记录两个方向的贡献：

    1
    int v0 = c[w[x] + d[x]][0], v1 = c[w[x] - d[x] + n][1];

  • x与所有子树的差分值合并之后得到的新贡献 - 旧贡献，不就是x所求吗！

    道理很简单，计数满足区间可减性，进入后的计数 = 进入前的计数 + 变化量

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void dfs(int x, int f) {
      int v0 = c[w[x] + d[x]][0], v1 = c[w[x] - d[x] + n][1];
      for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == f) continue;
        dfs(y, x);
      }
      for (auto it : a[x]) {
        int i = it.idx, v = it.value, k = it.kind;
        c[i][k] += v;
      }
      ans[x] = c[w[x] + d[x]][0] - v0 + c[w[x] - d[x] + n][1] - v1;
    }