Logic and Proofs

本文讨论 CCPC Final 2023 J 的与官方解法（from Lynkcat）略有区别的线性解法。

题目传送门：CCPC Final 2023 J

题解视频传送门：第九届 CCPC 总决赛题解

目前进度：

目前进度：

目前进度：

本文动笔的时候，博主距逃离人间天堂只差一门 17 号的考试，想着趁这个时间梳理一下自己寒假的计划，顺便立一下 flag。

目前进度：

目前进度：

知识与批判

理性思维与非理性思维

理性思维：根据知识解决问题、做出决定或取得理解的思维形式。

• 知识：能识别的，真(与事实相一致)的概念。

非理性思维：凭感觉、情绪、习惯(经验)等做出决定或取得理解的思维形式。

• 情绪、经验等驱动力是不稳定的，但会经常发生。

感觉 VS 认为

\(2019.6.29\ update:\)给出了时间复杂度的证明，更新了\(L_AT^EX\)

先引入一个问题：

1
2

给定一颗有n个节点的树，给定根节点
每次给出点对(x,y)，查询x到y路径上深度最小的节点(即LCA)。

看到这样的题目，大家首先想到的是暴力吧？

1. 从\(x\)出发向上走到根，标记每个经过的节点。

2. 从\(y\)出发向上走，经过的第一个有标记的节点就是"x到y路径上深度最小的节点"\((LCA)\)。

\(Code:\)

1
2
3
4
5
6
7
8
9

int LCA(int x,int y)
{
	if(x==y)return x;
	while(x!=root)vis[x]=true,x=fa[x];
	while(y!=root)
		if(vis[y])return y;
		else y=fa[y];
	return root;
}

但是让我们算算复杂度... \(\Theta(N)\ \)TLE

为什么复杂度如此之高？明显是因为走得太慢了。

我们需要更好的算法。

怎么做呢？

睿智的先人想到了倍增树剖

先把树剖分成一条条的链

每次直接跳一整条链，不就快了吗？

于是，树链剖分(\(Tree-chain\ Partition\))诞生了。