前言

这是课上讲过的题目，由于讲得蛮快的（其实是蒟蒻吸收得慢），所以我不得不再来捋一捋思路。

正文

题目链接：luoguP10289。

题面简单描述即是：有一个由$n$个点与$n-1$条边权为1的无向边构成的连通图（即是一棵树），点从1到$n$进行编号。同时，在这棵树上的结点中有$k$个特殊点两两之间连有一条“无形的”边权为0的无向边。给出$q$组询问，每组询问回答$u$点到$v$点的最短距离。

首先这是一棵边权为1的树，树上$u,\, v$两点距离应为$$dis(u,\, v)=depth(u)+depth(v)-2*depth(lca(u,\, v)).$$但特殊之处就在于“无形的”边，这样，树上$u,\, v$两点间的路径就不止一条。从最短距离考虑，发现事实上只会多出一条路径，即先从$u$点到距离$u$点最近的特殊点$a$，再从$a$点花费0到距离$v$点最近的特殊点$b$，最后从$b$到$v$。

那么现在，考虑求$f_{i}$表示$i$点到距离$i$点最近特殊点的距离，希望跑一遍树便能求出来。可以使每一个特殊点同时向四周扩散，若某个特殊点$s$率先扩散到某个未被标记的点$t$，则说明$t$点的最近特殊点为$s$，其间距离在扩散的同时记录即可；若扩散到已被标记的点，则停止该方向上的扩散，因为已经有别的特殊点率先扩散到该点并标记了它。那么，每个点只会被访问并标记一次，即只跑了一遍树。

最后答案就是$\min \{dis(u,\, v),\, f_{u}+f_{v}\}$。无核心代码，求了一个lca，再加上用于实现“扩散”的bfs求出$f_{i}$。整个bfs：

void bfs(){
	queue <pair <int, int> > que;
	memset(f, 0x3f, sizeof f);
	for(int i, u; i <= k; i++){
		cin >> u, f[u] = 0;
		que.push({u, 0}); // 特殊点先入队
	}
	while(!que.empty()){
		auto t = que.front();
		que.pop();
		for(int v : tree[t.first]){
			if(f[v] != 0x3f3f3f3f) continue; // 非极大值，已被标记
			f[v] = t.second + 1;
			que.push({v, f[v]});
		}
	}
}

后话

一篇文章只捋一道简单题太浪费了，可惜我时间太不充裕，以后只能精简思路描述了……