无法接受自己sT1T2没写出来

我在写这篇题解的时候cogs上时间限制还是1秒，cogs评测机显然不符合CCFIntel Core Ultra 9 285K CPU @ 3.70 GHz的标准，在洛谷和云斗AC的代码，再加上卡常也88分，最慢的1.099s，所以我打扰了老师开大时限，但老师可能比较忙没有回复，所以这篇题解在cogs上的分数按照1s为准。

题意

给你一张$N$个点无向图，保证任意两个点之间都是联通的。

另外还有$K$个额外的点，你可以从这$K$个点里任意选择若干个点，选择第$j$个点的代价为$c_j$，然后对于每个选择的点都可以往原本$N$个点连无向边，第$j$个额外点对第$i$个原有点连边的代价为$a_{j,i}$。

现在求出这张图的MST。

$1 \leq N \leq 10^4$

$1 \leq M \leq 10^6$

$0 \leq K \leq 10$

思路

考场淘汰回放：

把T1当成dp死做半天做不出来之后看第二题，一眼看第二题，先写出了60分左右的解法，代码还写了半天，结果一直以为和最短路有什么关系，恶心半天写不出来了

40~60分

直接把所有的边放到图里，包括额外点的连边。

排序所有边之后，枚举选额外点的状态跑kruskal即可。

粗略估计时间复杂度$O(2^k * (M+NK) log (M+NK))$（一共会有$M+NK$条边，枚举状态$2^k$）

不是满分，来看我回忆代码，不加赛时卡常，在cogs上就32分 云斗上80分 洛谷上88分

http://218.28.19.228:8081/cogs/submit/code.php?id=7XieaPkPU

https://www.yundouxueyuan.com/record/69072490b8ccc474dc719cef

https://www.luogu.com.cn/record/245035597

100分

我们最终选的边肯定包括了不考虑额外点的最小生成树里，所以先对原图跑一遍最小生成树，只保留树边，然后再枚举状态跑kruskal其实就做完了。

时间复杂度$O(M log M + 2 ^ k * (N - 1 + NK) log (N-1+NK))$

目前卡常在cogs88分，洛谷和云斗不卡常就是满分

太无聊了 写个水题题解吧（虽然赛时因为读错题被恶心了

题目大意

给你一个数组$A$，你需要选择若干个$A$中的**连续**段，使得每一段元素的异或和都是$K$。求最多选的段数。

$1 \leq n \leq 5 * 10^5$

思路

赛时没看到连续然后被卡半天

首先题目都说连续了，直接使用前缀和维护每一段的异或值，这里需要用到异或的逆运算，这里我手写了，实现很简单。

我们选择段的时候贪心的选，先把数组从前到后遍历一遍，还要维护一个set用来存储所有存在过的前缀异或值和一个总的异或值。

每次我们在set里查找一下有没有值满足对应的后缀能和当前的$a_i$匹配为$K$，我们记$a fxor b$为满足$b xor c = a$的$c$的值，那么我们就需要在set里查找$pre fxor (K fxor a[i])$，其中$pre$表示从最靠左的未匹配的位置到$i-1$之间所有元素的异或值。

如果在set里找到了符合条件的元素，也就是当前的$a_i$能够和一个后缀匹配成为一个异或和为$K$的连续段，那直接清空set，并把$pre$改为$0$，因为你后面考虑的就是下一段了，前面的就都不用管了，这样选的策略会让段的右端点尽量靠前就匹配，是最优的。

注意程序一开始要把set先插入一个$0$否则会WA

感谢ruyi为这篇题解作出的贡献。

题目大意

给你$N-K+1$个数，第$i$个数表示原数组$A$中第$i-K+1$到$i$的和。

现在问你有多少个01数组$A$满足上面的条件，保证至少存在一个$A$合法。

思路

我们发现$A$中的数取值只有$0$和$1$，不难想到给你的$N-K+1$个数里，相邻的两个数相差只有$0$,$1$和$-1$两种情况。

我们可以考虑维护一个数组$A$，初始化所有元素为$-1$，表示元素都没有确定。

如果相邻元素的差不是$0$，这两个元素的大小就是确定的，直接在$A$中修改；如果差是$0$，这两个元素就是一定相等的。

所以对于一个我们知道的相等的元素的集合，只要知道里面随便一个元素的值，整个集合都能确定，直接用DSU维护这个关系即可，实现很简单，实现很简单，直接把已知的$A_i$的值放到她的根节点上，再对于每个元素把她根结点的值放到自己上即可。

最后我们需要满足前$K$个元素是读入进来数组的第一个数，这堆连通块整体的方案数是$C(cnt1, s-cnt2)$，其中$cnt1$是我们连通块的数量，$cnt2$是我们确定的$1$的数量。

对.于后面的连通块，他们的取值怎么样都行，直接把答案乘$2$即可。

~~见过的最简单的一道蓝题（~~

一、 题目大意

• 核心描述：

给定一棵无根树（由 $N$ 个房间和 $N-1$ 条带权通道组成），以及三个道具位置 $A$、$B$、$C$。目标是找到一个汇合房间 $X$，使得 $A$、$B$、$C$ 到 $X$ 的路径长度之和最小。若有多个 $X$，输出房间编号字典序最小者（即编号最小）。

• 样例说明：

5 3 1 4
3 5 5
4 3 9
4 1 7
1 2 1

- 参数解析：$N=5$（5 个房间），$A=3$（某样道具在房间 3），$B=1$（某样道具在房间 1），$C=4$（某样道具在房间 4）。

- 树结构：边表示房间间通道及长度，形成树：

 - 房间 1 和 2 连接，长度 1。

 - 房间 1 和 4 连接，长度 7。

 - 房间 3 和 4 连接，长度 9。

 - 房间 3 和 5 连接，长度 5。

 - 等效路径：房间2 —(1)— 房间1 —(7)— 房间4 —(9)— 房间3 —(5)— 房间5。




距离计算：

- 到 $A=3$ 的距离：

 - 房间 3: 0

 - 房间 4: 9（直连边）

 - 房间 1: 9 + 7 = 16

 - 房间 2: 16 + 1 = 17

 - 房间 5: 5（直连边）

- 到 $B=1$ 的距离：

 - 房间 1: 0

 - 房间 2: 1

 - 房间 4: 7

 - 房间 3: 7 + 9 = 16

 - 房间 5: 16 + 5 = 21

- 到 $C=4$ 的距离：

 - 房间 4: 0

 - 房间 1: 7

 - 房间 3: 9

 - 房间 2: 7 + 1 = 8

 - 房间 5: 9 + 5 = 14

|room i| dis[i][A] | dis[i][B] | dis[i][C] |SUM_dis |
|------|-----------|-----------|-----------|--------|
| 1    | 16        | 0         | 7         | 23     |
| 2    | 17        | 1         | 8         | 26     |
| 3    | 0         | 16        | 9         | 25     |
| 4    | 9         | 7         | 0         | 16     |
| 5    | 5         | 21        | 14        | 40     |

输出分析：最小距离和为 $16$，在房间 $4$ 汇合（无其他房间相同和）。因此输出房间编号 $4$ 和距离和 $16$，符合样例输出。

二、 思路解析

第一层：解题基石

• 算法/数据结构选择：

邻接表存树 + BFS

• 选择原因：

- 树的性质利用：由于树中任意两点间路径唯一且无环，从单点出发到所有其他点的最短路径可通过一次 $BFS$ 或 $DFS$ 计算（边权为正，无需 $Dijkstra$）。

- 关键观察：最小距离和的点一定在 $A$、$B$、$C$ 三点形成的子树中，但为简化实现，可直接计算所有房间到 $A$、$B$、$C$ 的距离（时间复杂度 $O(N)$，$N \leq 20,000$ 可接受）。

第二层：思维脉络

• 关键步骤拆解：




1. 从 $A$ 点执行 $BFS/DFS$，计算每个房间到 $A$ 的距离，存储数组 $distA$。

2. 同理，从 $B$ 点计算 $distB$，从 $C$ 点计算 $distC$。

3. 遍历所有房间 $i$（从 $1$ 到 $N$），计算总距离和 $S_i = \text{distA}[i] + \text{distB}[i] + \text{distC}[i]$。

4. 找到 $S_i$ 最小的房间，若有多个，选 $i$ 最小者。

第三层：难点与陷阱

• 本题的易错点：

距离和访问标记数组的初始化和更新、$BFS$ 多次调用前的环境参数初始化处理是易错点；

• 你是如何思考的：

起初想建图，跑最短路算法，后发现是树形结构，房间之间路径唯一，且通过遍历可以在 $O(N)$ 时间内即可求得到其他所有点的距离，故选 $BFS$。

三、 代码实现

• 程序填空：




#include<bits/stdc++.h>
using namespace std;

const int N = ___; //房间数上限
const int MX = ___; //无穷大边界

//可以用struct或pair定义边
vector<___> graph[___];  // 邻接表存储树：边{v, w} 存入graph[u]
int disA[___], disB[___], disC[___];  // 分别存储到A、B、C的距离
int n, a, b, c;
int visited[___]; //访问标记数组

// BFS计算单源最短路径（树是无环的，BFS足够）
void bfs(int start, int dis[]) {//由于多次调用BFS，故把disA[],...B[],...C[]直接传给函数中的dis[]
	//Bfs函数中数组的传递方式，其核心是传递数组的首地址（即指针），这使得在函数内部可以直接修改主函数中数组的值。
	memset(___, ___, ___); //初始化 dis[]
	memset(___, ___, ___); //初始化 visited[]
	dis[start] = ___; //起点距离初始化
	___ //定义队列q
	___//起点入队 且 标记起点已访问
	while (___)  {//当队列不空
		___ //取出队头u
		for (___) {//枚举graph[u]中 u 的每一个邻接点 v
			int v = ___; //邻接点
			int w = ___; //边权
			//如果 v 未访问
				dis[v] = ___; //更新dis[v]
				___ //标记 v 已访问 且 入队
			
		}
	}
}

int main() {
	freopen("___.___", "___", ___);
	freopen("___.___", "___", ___);
	// 读取输入
	cin >> n >> a >> b >> c; //房间数，三人所在房间ABC
	for (int i = 1; i < ___; i++) {
		int u, v, w;
		//输入边，并建图
	}
	
	// 计算从A、B、C出发到所有点的距离
	bfs(a, disA); //bfs计算A到其他点的距离
	bfs(b, ___); //亦然
	bfs(c, ___); //亦然
	
	// 寻找最优汇合点
	int bestRoom = ___; //最佳房间号初始化
	int minSum = ___;  //最短距离之和初始化
	
	for (int i = 1; i <= n; i++) {//枚举所有房间，寻找最佳汇合点
		___
	}
	
	// 输出结果
	cout << ___ << ___ <<  ___ << endl;
	return 0;
}




• 复杂度分析：
  • 时间复杂度：

  $O(N)$（三次 $BFS/DFS$ 加一次遍历）。

  • 空间复杂度：

  $O(N)$（三个距离数组和三次 $BFS$ 遍历使用的队列）。

四、 总结与反思

• 收获与心得：

通过本题，我深刻理解了树结构在算法设计中的优越性。由于树的特殊性质（任意两点间路径唯一、无环），许多在图论中复杂的问题在树上可以简化为高效的线性或近似线性算法。这提醒我在解决实际问题时，首先要分析数据结构的特性，充分利用特定结构的性质来优化算法设计。特别是 $BFS/DFS$ 在树上的应用，相比通用图的最短路径算法（如 $Dijkstra$）更加高效简洁。

• 举一反三：

本题可以作为图论入门向进阶过渡的典型题目。它比简单的单源最短路径问题复杂，但又比网络流、强连通分量等高级图论算法简单，非常适合用来训练选手对图论基础知识的综合运用能力，如 $BFS/DFS$ 遍历、邻接表存储、距离计算等核心技能。

本题可以迁移到信息学奥赛中常见的"$树上多源最短路径$"类题目。这类题目通常给定一棵树和多个关键点，要求找到一个点使得所有关键点到该点的距离之和最小或最大。类似的题目包括寻找 $树的中心$、$重心$等 概念相关的问题，都需要计算树上多点间的距离关系。

该问题与运用 $LCA$ 技术解决的题目高度相关。在信息学奥赛中，很多树上路径问题都需要借助 $LCA$ 来高效计算两点间距离。虽然本题可以通过三次 $BFS$ 解决，但对于更大的数据规模或更复杂的需求，通常会使用 $LCA$ 加树上差分等高级技巧来优化计算过程。

五、 推荐题目

• $SYOI-594$. 树的重心

• $SYOI/COGS$ 服务点设置类的几个题

前言

由 zlc 和 fhx 提供的思路，orz。

貌似是 COGS 目前的最优解？（可能是其他人的常数太大了）

思路分析

先考虑一个经典的 dp，设 $f_i$ 表示将 $1\sim i$ 划分为若干好数组的方案，则有转移 $f_i=\sum f_{j-1}$，其中满足 $[j,i]$ 是一个好区间。

这样枚举 $i$，枚举 $j$，$O(n)$ 检测，就有 $O(n^3)$ 的 dp 了。注意到 $n\le 5\times 10^5$，考虑优化。

不难发现好的子数组在原数组中，要么是奇数位置为轻元素，偶数位置为重元素；要么是偶数位置为轻元素，奇数位置为重元素，所以我们分两种情况转移：分别是以 $i$ 结尾，奇数位置为轻元素和 $i$ 结尾，偶数位置为轻元素。两者本质没有区别，我们依靠前者讨论。

我们考虑区间左端点 $j$ 可以取到哪些位置，考虑对于任意 $x\in [1,i]$，元素 $x$ 对左端点 $j$ 的约束。

1. 若 $x$ 为奇数位置，作为轻元素约束 $j$。

则 $j$ 必须满足 $[lst_x+1,n]$，即对于任意 $i\in [1,n]$，只要 $j\in [lst_x+1,n]$，区间 $[j,i]$ 就可以满足 $x$ 的限制。

证明不难，当 $j\in [lst_x+1,x]$ 时，区间至多包含一个 $x$。当 $j>x$，区间一个 $x$ 都没有，自然无法约束。

容易发现，对 $j$ 的限制个数是奇数位置所有位置。

2.若 $x$ 为偶数位置，作为重元素约束 $j$

这种情况较为复杂。

首先可以发现对 $j$ 限制个数是元素种类数，对于同一种元素，我们用这种元素在 $[1,i]$ 中最后一次出现的位置来约束 $j$。

记 $p$ 为上一个在奇数位置出现的 $x$，$q$ 为 $x$ 上一次出现的位置。当 $j\le q$ 时，$[i,j]$ 一定包含了 $q,x$，满足重元素的限制，当 $j\le p$ 时，$p$ 作为重元素出现在奇数位置，$[i,j]$ 不合法，所以 $x$ 的限制是 $j\in [q+1,p]\cup[x+1,n]$。

注意：此时是按照 $x$ 是 $[1,i]$ 最后一次出现的数，随着 $i$ 的右移，如果在偶数位置出现一个和 $x$ 一样的元素 $y$。就要先撤销 $x$ 的限制，然后加入 $y$ 的限制。

考虑如何维护满足限制的端点：维护每个位置满足限制的个数，不难维护出限制的总个数，对于一个位置，如果它足一个限制，就让他的标记数组加一。如果一个位置满足的限制个数为总个数，就说明 $[j,i]$ 是一个合法的端点。

注意一种特殊情况是 $[i,i]$ 是合法区间，我们只统计 $j\in [1,i-1]$ 的合法左端点。

直接用数组模拟是 $O(n^2)$，容易用线段树优化到 $O(n\log n)$，具体的记录每个区间任意位置满足限制个数最大值，满足限制个数达到这个最大值的 $f_{i-1}$ 之和，pushup 分讨一下即可。

然后这个问题就解决了。

先创建一个 $map$，使 $m[队列元素]=$队列编号，这样后面好查找元素的组别；

再创建一个队列 $q[301]$，$q[i]$ 表示队列编号为 $i$ 的排队情况。$q[0]$ 表示小组的排序；

队列输入不用多说，只需要注意一个新小组的人入队要给新小组排上队；

队列输出时查看 $q[0]$ 队头，看到小组编号后查该小组的队头，再输出，注意小组的人全部出队后要把空小组删掉。