第二届天元编程邀请赛(提高组) 解题报告

一场相当有收获的比赛。比赛链接

A – 石老板举世无双

解法一

尝试观察规律。我们发现,在完成ss次操作以后,左端点的可能取值为xa+(2sx)b2s,x[1,2s]\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s],右端点的可能取值为xa+(2sx)b2s,x[0,2s)\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)。假如现在我们达到最终状态,其l=(x+1)a+(2sx1)b2s,r=xa+(2sx)b2sl=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}。那么,在xx的二进制表示中,如果从高到底pos\mathrm{pos}位为11,则在第pos\mathrm{pos}轮中,有check (mid) == 0,向右区间递归;否则向左区间递归。这是很容易解释的:若向右递归,则右端点不变。而在下一层,右端点表示中a,ba, b的所有系数乘22,所以体现为二进制位末尾添一个00。反之,就变成(x+(x+1))/2(x+(x+1))/2,在下一层中体现为2x+12x+1。如果其有popc(x)\operatorname{popc}(x)位为11,则到达该状态的概率为p0popc(x)p1spopc(x)p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}

s=3s=3时的状态l=3a+5b8,r=2a+6b8l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}为例。22的三位二进制表示为0b010\text{0b010},则推断出在前三轮分别向右、左、右区间递归,到达其的概率为p0p12p_0p_1^2

考虑计算一个状态的贡献。有E(X)=ipixiE(X)=\sum\limits_i p_ix_i,程序最终输出(l+r)/2(l+r) / 2,则我们需要求x=02s1(2x+1)a+(2s+12x1)b2s+1p0popc(x)p1spopc(x)\sum_{x=0}^{2^s-1}\frac{(2x+1)a+(2^{s+1}-2x-1)b}{2^{s+1}}p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}。存在p0,p1p_0, p_1的高次项,不好处理,所以我们考虑合并处理popc(x){\operatorname{popc}(x)}相同的项。我们钦定popc(x)=k\operatorname{popc}(x)=k,则易得所有这样的xx的和为(2s1)(s1k1)(2^s-1)\dbinom{s-1}{k-1}(计算每一位对总和的贡献。钦定在kk11中必须选择第tt位,其他位位置任选,共有(s1k1)\dbinom{s-1}{k-1}种选择;该位的贡献为2t(s1k1)2^t\dbinom{s-1}{k-1},有t=0s12t=2s1\sum\limits_{t=0}^{s-1}2^t=2^s-1),这样的xx共有(sk)\dbinom{s}{k}个。因此上述式子可以转写为k=0s((2(2s1)(s1k1)+(sk))(ab)2s+1+(sk)b)p0kp1sk\sum\limits_{k=0}^{s}\left(\frac{\left(2(2^s-1)\binom{s-1}{k-1}+\binom{s}{k}\right)(a-b)}{2^{s+1}}+\binom{s}{k}b\right)p_0^kp_1^{s-k}

直接代入上述式子计算,可以得到60 pts\textbf{60 pts}的好成绩。

(实际上在考场上推出的式子略微不同,但本质上只是调换了aa一项的计算顺序。)

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
constexpr int N = 1e7 + 10, P = 998244353, inv100 = 828542813; ll a, b, s, p0, p1; int powp1, powp0, invp0, ans, suma, sumb; int fact[N], finv[N], pow2s1, invpow2s1, pow2s1m2; inl ll fpow (ll a, ll b) { ll res = 1; a %= P; for (; b; b >>= 1) { if (b & 1) res = res * a % P; a = a * a % P; } return res; } inl void calc_inv (int lmt) { fact[0] = 1; for (ll i = 1; i <= lmt; ++i) fact[i] = fact[i - 1] * i % P; finv[lmt] = fpow (fact[lmt], P - 2); for (int i = lmt - 1; ~i; --i) finv[i] = finv[i + 1] * (i + 1ll) % P; pow2s1 = fpow (2, s + 1); pow2s1m2 = (pow2s1 - 2 + P) % P; invpow2s1 = fpow (pow2s1, P - 2); powp1 = 1, powp0 = fpow (p0, s); invp0 = fpow (p0, P - 2); } inl ll C (int x, int y) { if (y < 0) return 0; return x < y ? 0 : 1ll * fact[x] * finv[x - y] % P * finv[y] % P; } int main () { /* MOCK NOIP 20220514 吴秋实 */ read (a, b, s, p0, p1); p0 = 1ll * p0 * inv100 % P, p1 = 1ll * p1 * inv100 % P; calc_inv (s + 2); for (int k = 0; k <= s; ++k) { suma = (C (s - 1, s - k - 1) * pow2s1m2 + C (s, k)) % P; sumb = (C (s, k) * pow2s1 - suma + P) % P; (ans += (1ll * suma * a + 1ll * sumb * b) % P * invpow2s1 % P * (1ll * powp0 * powp1 % P) % P) %= P; powp0 = 1ll * powp0 * invp0 % P, powp1 = 1ll * p1 * powp1 % P; } print (ans); return 0; }

能不能对它化简?答案是肯定的。我们继续合并同类项。\begin{align}

发现两个式子分别可以由二项式定理得到常数和。这样我们就可以在O(logn)\mathrm{O}(\log n)的时间内计算快速幂求和了。

(其实在场上是通过Python暴力打表发现的规律……雾

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
constexpr int P = 998244353, inv100 = 828542813; ll a, b, s, p0, p1, ans; ll fpow (ll a, ll b) { ll res = 1; a %= P; for (; b; b >>= 1) { if (b & 1) res = res * a % P; a = a * a % P; } return res; } #define inv(x) fpow((x), P - 2) int main () { /* */ read (a, b, s, p0, p1); ans = (fpow (2, s) - 1) * inv (fpow (2, s)) % P * (a - b + P) % P * (p0 * inv100 % P) % P + (a + (fpow (2, s + 1) - 1) * b % P) * inv (fpow (2, s + 1)) % P; print (ans % P); return 0; }

解法二

实际上,根据期望的线性性就可以求解。

E(Δl)E(\Delta l)llss次操作以后期望右移的距离。由于每一轮操作独立,每一轮结束后区间长度一定,故有\begin{align}E(\Delta l) & = \sum_{k=1}^{s}p_0\cdot 0+p_1\dfrac{b-a}{2^k}

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
constexpr int P = 998244353, inv100 = 828542813; ll a, b, s, p0, p1, ans; inl ll fpow (ll a, ll b) { ll res = 1; a %= P; for (; b; b >>= 1) { if (b & 1) res = res * a % P; a = a * a % P; } return res; } #define inv(x) fpow((x), P - 2) #define proc(x) (((x) % P + P) % P) int main () { /* */ read (a, b, s, p0, p1); ans = inv (2) * ((a + b + (b - a + P) * proc (p1 * inv100 - p0 * inv100) % P * (fpow (2, s) - 1) % P * inv (fpow (2, s)) % P) % P); print (ans % P); return 0; }

解法三(题解做法)

考虑DP。设f(x)f(x)为经过xx轮操作后ll的期望位置,g(x)g(x)rr的期望位置,则根据期望的线性性有以下转移:f(x)=p0f(x)+p1f(x)+g(x)2g(x)=p1g(x)+p0g(x)+f(x)2\begin{align}f(x)=p_0f(x)+p_1\frac{f(x)+g(x)}{2}\\ g(x)=p_1g(x)+p_0\frac{g(x)+f(x)}{2}\end{align},使用矩阵乘法加速递推即可。代码容易实现。

B – 石老板腾云驾雾

容易发现,设数xx的因数中,能够找到的最大完全平方数为g(x)=i=1kpici,2cig(x)=\sum\limits_{i=1}^{k}p_i^{c_i}, 2 \mid c_i,且令x=xg(x)x’=\dfrac{x}{g(x)},则不能够同时选择两个相同的xx’,否则其乘积必为完全平方数;两个不同的xx’相乘,必然会存在次数为奇数的某个质因子,不是完全平方数。因此我们暴力分解其质因数求出不同xx’的个数就是答案。

赛后翻看他人AC代码,发现一个精妙的优化:我们只需要筛查x3\sqrt[3]{x}以内的质因数。xx至多存在两个质因数p1,p2>x3p_1, p_2>\sqrt[3]{x},这时若其二者相同(乘积为完全平方数)则不考虑它们;否则它们的次数均为11,将包含在xx’中。可以使用 sqrt 函数以常数时间判断。

综上,如果作质数筛预处理,时间复杂度为O(nmax{a}3lnmax{a}3+nlogn)\mathrm{O}(n \dfrac{\sqrt[3]{\max\{a\}}}{\ln \sqrt[3]{\max\{a\}}}+n \log n)

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
constexpr int N = 1e5 + 10, G = 1e3; int n, x, fac[G+1], p[G>>2], pcnt; set <int> g; void sieve () { for (int x = 2; x <= G; ++x) { if (!fac[x]) fac[x] = p[++pcnt] = x; for (int i = 1; i <= pcnt && p[i] <= fac[x] && p[i] * x <= G; ++i) fac[p[i] * x] = p[i]; } } int _defac (int x) { int c = 0, p = 0, res = 1; while (x > 1) { if (fac[x] == p) ++c; else { if (c & 1) res *= p; c = 1, p = fac[x]; } x /= fac[x]; } if (c & 1) res *= p; return res; } int defac (int x) { if (x <= G) return _defac (x); int res = 1, c = 0, ori = x; for (int i = 1; i <= pcnt && p[i] * p[i] * p[i] <= ori; ++i) { if (x % p[i]) continue; c = 0; while (x % p[i] == 0) x /= p[i], ++c; if (c & 1) res *= p[i]; if (x <= G) return _defac (x) * res; } return ((int) sqrt (x) * (int) sqrt (x) == x) ? res : x * res; } int main () { /* MOCK NOIP 20220514 吴秋实 */ read (n); sieve (); for (int i = 1; i <= n; ++i) read (x), g.insert (defac (x)); print (g.size ()); return 0; }

C – 石老板心肌梗塞

由题意可得,假如w=1,2,,ans1w=1,2,\cdots,\text{ans}-1的路径均有至少11条没有经过ee,而有w=answ=\text{ans}路径全部经过该边/在图上不存在,则答案就是ans\text{ans}。因此我们要求的就是满足“权值为ww的路径全部经过边ee”的最小的ww

自然想到,我们可对每一条路径作树上差分,在路径(u,v)(u, v)的两端点和lca(u,v)\operatorname{lca}(u, v)处分别加入/取消ww的一次覆盖,则在某一条边上,我们求所有满足上述条件的权值集合的最小值即可。通过动态开点权值线段树、树上差分线段树合并,在加入/取消ww的覆盖时检查其计数是否等于ww的全体路径数并更新该线段树的答案,就可以得到一个空间复杂度为O(mlogm)\mathrm{O}(m \log m),时间复杂度为O(mlogm+mlogn)\mathrm{O}(m \log m+m \log n)的解。期望得分80 pts\textbf{80 pts}(据说如果卡常够好可以AC……

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
  86. 86
  87. 87
  88. 88
  89. 89
  90. 90
  91. 91
  92. 92
  93. 93
  94. 94
  95. 95
  96. 96
  97. 97
constexpr int N = 5e5 + 10, M = 2e6 + 10, INF = 0x3f3f3f3f; int n, m, x, y, ecnt = 1, z, head[N]; int fa[N], dfn[N], tot, top[N], gcnt[N], lmt; int dep[N], siz[N], hson[N], ans[N]; struct path { int x, y, z; } g[M]; struct edge { int v, nxt; } e[N<<1]; inl void add_e (int x, int y) { e[++ecnt] = { y, head[x] }, head[x] = ecnt; } void dfs (int x, int fr) { dep[x] = dep[fa[x] = fr] + 1; for (int i = head[x]; i; i = e[i].nxt) { if (e[i].v == fr) continue; dfs (e[i].v, x); siz[x] += siz[e[i].v]; if (siz[e[i].v] > siz[hson[x]]) hson[x] = e[i].v; } ++siz[x]; } void decomp (int x, int tp) { dfn[x] = ++tot; top[x] = tp; if (!hson[x]) return; decomp (hson[x], tp); for (int i = head[x]; i; i = e[i].nxt) if (e[i].v != fa[x] && e[i].v != hson[x]) decomp (e[i].v, e[i].v); } int lca (int x, int y) { while (top[x] != top[y]) dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]]; return dep[x] > dep[y] ? y : x; } struct node { int ls, rs, cnt, mn; } t[M*15]; int rt[N], ntot; #define post(x) (t[x].mn = min (t[t[x].ls].mn, t[t[x].rs].mn)) void upd (int &x, int l, int r, int tar, int dt) { if (!x) t[x = ++ntot] = { 0, 0, 0, INF }; if (l == r) { t[x].cnt += dt; t[x].mn = t[x].cnt == gcnt[l] ? l : INF; return; } int mid = l + r >> 1; tar <= mid ? upd (t[x].ls, l, mid, tar, dt) : upd (t[x].rs, mid + 1, r, tar, dt); post (x); } int merge (int p, int q, int l, int r) { if (!p || !q) return p | q; if (l == r) { t[p].cnt += t[q].cnt; t[p].mn = t[p].cnt == gcnt[l] ? l : INF; return p; } int mid = l + r >> 1; t[p].ls = merge (t[p].ls, t[q].ls, l, mid); t[p].rs = merge (t[p].rs, t[q].rs, mid + 1, r); post (p); return p; } void imple (int x, int fre) { int y; for (int i = head[x]; i; i = e[i].nxt) { if ((y = e[i].v) == fa[x]) continue; imple (y, i); rt[x] = merge (rt[x], rt[y], 1, m); } ans[fre>>1] = min (lmt, t[rt[x]].mn); } int main () { /* MOCK NOIP 20220514 吴秋实 */ #ifdef LOCAL freopen ("c.in", "r", stdin); freopen ("c.out", "w", stdout); #endif read (n, m); t[0].mn = INF; for (int i = 1; i < n; ++i) read (x, y), add_e (x, y), add_e (y, x); dfs (1, 0); decomp (1, 1); for (int i = 1; i <= m; ++i) read (g[i].x, g[i].y, g[i].z), ++gcnt[g[i].z]; for (int i = 1; i <= m; ++i) { x = g[i].x, y = g[i].y, z = g[i].z; upd (rt[x], 1, m, z, 1), upd (rt[y], 1, m, z, 1), upd (rt[lca (x, y)], 1, m, z, -2); } lmt = 1; while (gcnt[lmt]) ++lmt; imple (1, 0); for (int i = 1; i < n; ++i) print (ans[i]), newl; return 0; }

但这还不够,需要空间和时间的利用都更加高效的解法。实际上,对于固定的权值ww,我们只关心所有权值为ww的路径的交集,只有这些边的答案有可能是ww。这就引申出一个经典问题:快速求解两条路径的边的交集。此处给出结论:设两条路径为(x,y),(a,b)(x, y), (a, b),有l1=lca(x,a),l2=lca(x,b),l3=lca(y,a),l4=lca(y,b)l_1=\operatorname{lca}(x, a), l_2=\operatorname{lca}(x, b), l_3=\operatorname{lca}(y,a), l_4=\operatorname{lca}(y, b),则取l1,2,3,4l_{1, 2, 3, 4}中深度最大的两个点,记作u,vu, v。若uvu \neq v,则(u,v)(u, v)即为路径交集;否则两条路径不存在交。可以通过分类讨论验证该结论。

接下来,我们优化答案的更新。假如我们求出所有权值为ww的路径的交(x,y)(x, y)。我们考虑尽可能不更新该路径上已经确定答案的边。定义up(x)\operatorname{up}(x)在上一次访问(并在第一次访问时确定答案)后,在xx的所有祖先节点中,已知还未确定答案的深度最小的节点编号。由此,我们可以“暴力”遍历(x,lca(x,y)),(y,lca(x,y)(x, \operatorname{lca}(x, y)), (y, \operatorname{lca}(x, y)的节点,每次跳到up(x)\operatorname{up}(x)并尝试更新答案,同时尝试更新up(x)\operatorname{up}(x)。其本质上是只采用路径压缩的变种并查集,每次操作的均摊时间复杂度为Ω(α(n))O(logn)\Omega(\alpha(n))-\mathrm{O}(\log n)

lca\operatorname{lca}时还可以使用欧拉序列配合RMQ在常数时间内求解,复杂度瓶颈转移到预处理ST表上(O(nlogn)O(1)\mathrm{O}(n \log n)-\mathrm{O}(1))。(实测比树剖LCA跑得慢

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
constexpr int N = 5e5 + 10, M = 2e6 + 10; int n, m, x, y, z, ecnt = 1, head[N], tot; int up[N], eid[N], dep[N], occ[N], log2s[N<<1]; vector <pint> g[M]; int st[N<<1][21]; array <int, 4> llst; int ans[N]; struct edge { int v, nxt; } e[N<<1]; inl void add_e (int x, int y) { e[++ecnt] = { y, head[x] }, head[x] = ecnt; } void dfs (int x, int fr) { dep[x] = dep[fr] + 1, up[x] = fr; st[++tot][0] = x; occ[x] = tot; int y; for (int i = head[x]; i; i = e[i].nxt) { if ((y = e[i].v) == fr) continue; dfs (y, x); eid[y] = i>>1; st[++tot][0] = x; } } int comp (int x, int y) { return dep[x] > dep[y] ? y : x; } void build_st () { log2s[0] = -1; for (int i = 1; i <= n<<1; ++i) log2s[i] = log2s[i>>1] + 1; for (int w = 1; (1<<w) < (n<<1); ++w) for (int i = 1; i + (1<<w) - 1 <= n<<1; ++i) st[i][w] = comp (st[i][w - 1], st[i + (1<<w-1)][w - 1]); } int lca (int x, int y) { x = occ[x], y = occ[y]; if (x > y) swap (x, y); int w = log2s[y - x + 1]; return comp (st[x][w], st[y - (1<<w) + 1][w]); } int main () { /* */ read (n, m); for (int i = 1; i < n; ++i) read (x, y), add_e (x, y), add_e (y, x); for (int i = 1; i <= m; ++i) read (x, y, z), g[z].emplace_back (x, y); dfs (1, 0); build_st (); for (z = 1; z <= m + 1; ++z) if (!g[z].size ()) { for (x = 1; x < n; ++x) if (!ans[x]) ans[x] = z; break; } else { auto [p, q] = g[z].back (); g[z].pop_back (); for (const auto [x, y] : g[z]) { llst = { lca (x, p), lca (x, q), lca (y, p), lca (y, q) }; sort (all (llst), [] (int x, int y) { return dep[x] > dep[y]; }); p = llst[0], q = llst[1]; if (p == q) break; } int l = lca (p, q); while (dep[p] > dep[l]) { if (!ans[eid[p]]) ans[eid[p]] = z; x = up[p], up[p] = comp (up[p], l), p = x; } while (dep[q] > dep[l]) { if (!ans[eid[q]]) ans[eid[q]] = z; x = up[q], up[q] = comp (up[q], l), q = x; } } for (int i = 1; i < n; ++i) print (ans[i]), newl; return 0; }

D – 石老板魂飞魄散

易得将同色连通块合并后仍然形成树形结构。对于每个连通块,以现存儿子的颜色为键值,记录每个颜色都有哪些儿子。更改颜色时,更新父亲的儿子信息即可,同时检查是否能合并儿子/被父亲合并。如果发生合并,启发式合并两个连通块记录儿子信息的数据结构。

实现时需要注意细节。例如,为了保证每个连通块编号的唯一性,采取其在树上深度最小��节点作为代表元素。使用并查集查询某个连通块实际的父亲的代表元素,并且回答题目中的询问;记录儿子信息时,为了达到均摊常数时间复杂度,可以使用哈希表和链表。(就这么简单

时间复杂度均摊O(mlogn)\mathrm{O}(m\log n)O(mlog2n)\mathrm{O}(m \log^2 n),取决于使用的数据结构。

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 64
  65. 65
  66. 66
  67. 67
  68. 68
  69. 69
  70. 70
  71. 71
  72. 72
  73. 73
  74. 74
  75. 75
  76. 76
  77. 77
  78. 78
  79. 79
  80. 80
  81. 81
  82. 82
  83. 83
  84. 84
  85. 85
constexpr int N = 1e6 + 10; int n, m, fa[N], x, y, z, a[N], opt; vector <int> e[N], slst; int rtfa, rep[N], sonc[N]; unordered_map <int, list <int>> conn[N]; list <int>::iterator b[N]; struct dsu { int fa[N], siz[N]; inl void init (int n) { for (int x = 1; x <= n; ++x) fa[x] = x, siz[x] = 1; } int get (int x) { return fa[x] == x ? x : fa[x] = get (fa[x]); } inl void merge (int x, int y) { // ? 将x合并到y上。 x = get (x), y = get (y); if (x == y) return; if (siz[x] > siz[y]) rep[x] = rep[y], swap (x, y); siz[y] += siz[x], fa[x] = y; } } d; bool vis[N]; void span (int x) { vis[x] = 1; for (const int y : e[x]) if (a[y] == a[x] && !vis[y]) span (y), d.merge (y, x); } void insert (int bel, int x) { conn[bel][a[x]].push_front (x); b[x] = conn[bel][a[x]].begin (); ++sonc[bel]; } void remove (int bel, int x) { conn[bel][a[x]].erase (b[x]); --sonc[bel]; } void merge (int rt, int rtfa) { remove (rtfa, rt); d.merge (rt, rtfa); if (sonc[rt] > sonc[rtfa]) conn[rtfa].swap (conn[rt]); for (const auto &[col, lst] : conn[rt]) for (const int id : lst) insert (rtfa, id); } int main () { /* MOCK NOIP 20220514 吴秋实 */ read (n, m); d.init (n); for (x = 2; x <= n; ++x) read (fa[x]), e[fa[x]].push_back (x); for (x = 1; x <= n; ++x) read (a[x]); for (x = 1; x <= n; ++x) if (!vis[x]) rep[x] = x, span (x), insert (rep[d.get (fa[x])], x); for (int i = 1; i <= m; ++i) { read (opt); if (opt == 2) read (x), print (d.siz[d.get (x)]), newl; else { read (x, y); int rt = rep[d.get (x)]; if (fa[rt]) remove (rtfa = rep[d.get (fa[rt])], rt), a[rt] = y, insert (rtfa, rt); else a[rt] = y; if (conn[rt].find (y) != conn[rt].end ()) { slst.assign (all (conn[rt][y])); conn[rt].erase (y); sonc[rt] -= slst.size (); for (const int son : slst) merge (son, rt); } if (fa[rt] && a[rtfa] == y) merge (rt, rtfa); } } return 0; }
  • 2022年5月17日