LOJ6674 赛道修建

Posted on | In

一道暴力 bitset 配合 DP 的题。

以后遇到这种题应当考虑使用 bitset。

题意

给定一棵树，其中有若干个点被钦定是好的。称一条长度可为 $0$ 的有向简单路径是好的，当且仅当这个路径的终点为好的。对于每个点 $u$，以它为起点的好路径可能有很多条，请分别计算出长度种类数。

$n\le 50000$，TL 3s，ML 1G。

link: https://loj.ac/p/6674

思路

暴力地对每个点维护一个 bitset 来统计每个长度是否出现过。

首先维护一个 $fu$ 表示只考虑子树 $u$ 时 $u$ 的长度出现情况。容易推出转移式 $f_u=\left(\left(\mathop\odot\limits{v\in\operatorname{son}_u}f_v\right)\ll 1\right)\odot c_u$，其中 $c_u$ 是 $u$ 是否被钦定，$\odot$ 是按位或。

接下来维护一个 $gu$ 表示子树 $u$ 以外的点对 $u$ 的长度出现情况。容易推出转移式 $g_u=(g{\operatorname{fa}(u)}\ll 1)\odot\mathop\odot\limits{v\in\operatorname{son}{\operatorname{fa}(u)}\land v\ne u} (f_v\ll 2)$。不过后一个和式不好转移。

考虑给每个结点的儿子定序，则每个结点所需的值为其前面所有兄弟以及后面所有兄弟之按位或。维护一个全局的暂存 bitset，先从前往后扫一遍，一边维护前缀或一边按位或给儿子的 $g$ 值；再从后往前扫一遍。这样仅需要存 $2n+O(1)$ 个长为 $n$ 的 bitset，预计空间约为 625MB，可以通过本题。

@kunyi 同学提供了一个做法：维护 $3n+O(1)$ 个长为 $\dfrac n2$ 的 bitset，预计空间 468.75MB，由于数据比较水就过了……

代码

link: https://loj.ac/s/1415501

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
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstdlib>

namespace mirai {

constexpr int MAXN = 50005;
int can[MAXN], fa[MAXN], ans[MAXN];
std::vector<int> graph[MAXN];
std::bitset<MAXN> buf, son[MAXN], anc[MAXN];

void dfs(int u, int f) {
  fa[u] = f;
  son[u][0] = can[u];
  for (std::size_t i = 0; i < graph[u].size(); ++i) {
    if (graph[u][i] == f) {
      graph[u].erase(graph[u].cbegin() + i);
      --i;
      continue;
    }
    dfs(graph[u][i], u);
    son[u] |= son[graph[u][i]] << 1;
  }
}

void dfs2(int u) {
  anc[u][0] = can[u];
  ans[u] = (son[u] | anc[u]).count();
  buf = anc[u];
  for (std::size_t i = 0; i < graph[u].size(); ++i) {
    anc[graph[u][i]] |= buf << 1;
    buf |= son[graph[u][i]] << 1;
  }
  buf = anc[u];
  for (int i = graph[u].size() - 1; i >= 0; --i) {
    anc[graph[u][i]] |= buf << 1;
    buf |= son[graph[u][i]] << 1;
  }
  for (auto i : graph[u]) {
    dfs2(i);
  }
}

int main(int argc, char** argv) {
  int n;
  std::scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    std::scanf("%d", &can[i]);
  }
  for (int i = 1; i < n; ++i) {
    int u, v;
    std::scanf("%d%d", &u, &v);
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  dfs(1, 0);
  anc[1] = can[1];
  dfs2(1);
  
  for (int i = 1; i <= n; ++i) {
    std::printf("%d\n", ans[i]);
  }
  
  return 0;
}

} // namespace mirai

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}