数据结构 / 概率论 / 比赛日志

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

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

A – 石老板举世无双

解法一

尝试观察规律。我们发现，在完成ss次操作以后，左端点的可能取值为xa+(2s−x)b2s,x∈[1,2s]\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s]，右端点的可能取值为xa+(2s−x)b2s,x∈[0,2s)\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)。假如现在我们达到最终状态，其l=(x+1)a+(2s−x−1)b2s,r=xa+(2s−x)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)p1s−popc⁡(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=02s−1(2x+1)a+(2s+1−2x−1)b2s+1p0popc⁡(x)p1s−popc⁡(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的和为(2s−1)(s−1k−1)(2^s-1)\dbinom{s-1}{k-1}（计算每一位对总和的贡献。钦定在kk个11中必须选择第tt位，其他位位置任选，共有(s−1k−1)\dbinom{s-1}{k-1}种选择；该位的贡献为2t(s−1k−1)2^t\dbinom{s-1}{k-1}，有∑t=0s−12t=2s−1\sum\limits_{t=0}^{s-1}2^t=2^s-1），这样的xx共有(sk)\dbinom{s}{k}个。因此上述式子可以转写为∑k=0s((2(2s−1)(s−1k−1)+(sk))(a−b)2s+1+(sk)b)p0kp1s−k\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;
}

能不能对它化简？答案是肯定的。我们继续合并同类项。 原式=∑k=0s(2s−12s(s−1k−1)+a−b2s+1(sk)+b(sk))p0kp1s−k=2s−12s∑k=0s(s−1k−1)p0kp1s−k+a+(2s+1−1)b2s+1∑k=0s(sk)p0kp1s−k=2s−12sp0∑k=0s(s−1k−1)p0k−1p1s−k+a+(2s+1−1)b2s+1∑k=0s(sk)p0kp1s−k=2s−12sp0(p0+p1)s−1+a+(2s+1−1)b2s+1(p0+p1)s=2s−12sp0+a+(2s+1−1)b2s+1\begin{aligned} \textbf{原式} & = \sum_{k=0}^{s}\left(\frac{2^s-1}{2^s}\dbinom{s-1}{k-1}+\frac{a-b}{2^{s+1}}\dbinom{s}{k}+b\dbinom{s}{k}\right)p_0^kp_1^{s-k} \\ & = {\color{blue}\frac{2^s-1}{2^s}\sum_{k=0}^{s}\dbinom{s-1}{k-1}p_0^kp_1^{s-k}}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}\sum_{k=0}^{s}\dbinom{s}{k}p_0^kp_1^{s-k}} \\ & = {\color{blue}\frac{2^s-1}{2^s}p_0\sum_{k=0}^{s}\dbinom{s-1}{k-1}p_0^{k-1}p_1^{s-k}}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}\sum_{k=0}^{s}\dbinom{s}{k}p_0^kp_1^{s-k}} \\ & = {\color{blue}\frac{2^s-1}{2^s}p_0(p_0+p_1)^{s-1}}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}(p_0+p_1)^s} \\ & = {\color{blue}\frac{2^s-1}{2^s}p_0}+{\color{red}\dfrac{a+(2^{s+1}-1)b}{2^{s+1}}} \end{aligned}

发现两个式子分别可以由二项式定理得到常数和。这样我们就可以在 O(log⁡n)\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) 为 ll 在 ss 次操作以后期望右移的距离。由于每一轮操作独立，每一轮结束后区间长度一定，故有 E(Δl)=∑k=1sp0⋅0+p1b−a2k=p1(b−a)(1−12s)\begin{aligned}E(\Delta l) & = \sum_{k=1}^{s}p_0\cdot 0+p_1\dfrac{b-a}{2^k}\\ & = p_1(b-a)(1-\dfrac{1}{2^s}) \end{aligned}（只有p1p_1的概率右移）。右端点同理，将系数更换为p0p_0即可。所以有 E(ans)=(a+E(Δl)+b−E(Δr))/2=12(a+b+(b−a)(p1−p0)2s−12s)\begin{aligned}E(\text{ans}) & = (a+E(\Delta l)+b-E(\Delta r))/2 \\& =\dfrac{1}{2}\left(a+b+(b-a)(p_1-p_0)\dfrac{2^s-1}{2^s}\right)\end{aligned}

  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{aligned} 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{aligned}

使用矩阵乘法加速递推即可。代码容易实现。

B – 石老板腾云驾雾

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

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

综上，如果作质数筛预处理，时间复杂度为O(nmax⁡{a}3ln⁡max⁡{a}3+nlog⁡n)\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,⋯ ,ans−1w=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(mlog⁡m)\mathrm{O}(m \log m)，时间复杂度为O(mlog⁡m+mlog⁡n)\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。若u≠vu \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(log⁡n)\Omega(\alpha(n))-\mathrm{O}(\log n)。

求lca⁡\operatorname{lca}时还可以使用欧拉序列配合RMQ在常数时间内求解，复杂度瓶颈转移到预处理ST表上（O(nlog⁡n)−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(mlog⁡n)\mathrm{O}(m\log n)或O(mlog⁡2n)\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日

Tags:

You may also like...

1 Response

  1. MOCK NOIP 20221108 日志 – Charles Wu的博客
    2022年11月16日

    […] 这道题让我想起了天元编程邀请赛的 T3。 […]

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

成都外国语学校高二 OIer。喜欢搞些杂七杂八的小项目。常去骑车。复健中，脚力已不如前。

一言(ひとこと)

暫し空に祈りて 愛を断て

分类目录