[数据结构与算法][ACNOI2022]《普林斯普的荣光》

题目

题目背景
多年以后，我在搬砖的工地上，远远望见了一个身影：仍然是如同漆黑的杆子一般，手丝毫不摆动，而脚一步一印往前挪动，像吸盘，像祂正试图学会在地上平移，用自己的脚。

我几乎要失声叫出祂的名字；这个名字我花了十年去恐惧，花了十年去遗忘，但我看到祂的一瞬间，所有努力都是徒劳，所有意义都被抹杀。

任何事物都逃不过祂的眼睛。当我从惊慌中挣脱出来，抬头便遇上祂的审视。祂胸前的金牌扰乱着我的神志。我只能勉强从牙缝中挤出来几个字：

“普……普林斯普！”

祂的嘴唇没有动，我的脑海中却响起一句话。这真的是我刚刚所顿悟的么？

“校长笑话，烟雾弹也；水群摆烂，麻痹对手尔。”

回忆如波涛翻滚。仿佛有无数个祂同时在我耳边低语：

“你看，你又被骗了吧。”

题目描述
给出一个无向连通图 $G=(V,E)$，定义新图 $G^{\prime }=(V,E^{\prime })$ 满足 E ′ = { ? a , b , c a ? ∣ dis ( a , b ) ? d a } E'=\{\langle a,b,c_a\rangle\mid\text{dis}(a,b)\leqslant d_a\} E′={?a,b,ca??∣dis(a,b)?da?}，其中 $?a,b,c?$ 表示边权为 $c$ 的 $a\to b$ 有向边，而 $\text{dis}(a,b)$ 为 $G$ 上 $a,b$ 最短路的边数。

求新图 $G^{\prime }$ 上 $1$ 号点到每个点的最短路。

数据范围与约定
$n?2\times 10^5\wedge d_i\in [1,n]\wedge c_i\in [1,10^9]\wedge |E|?|V|+50$ 。时限 $4\mathrm{s}$ 。

思路

注意到 $|E|?|V|+50$，考虑建一棵生成树，然后讨论非树边的影响。必要条件是搞懂树边的影响。即，先考虑原图是一棵树的情况。

树上路径问题？类似此题，可以直接点分治优化建图。不需要边分治，因为 $\text{dis}(y,z)?d_x?\text{dis}(x,z)$ 是 $x\to y$ 有边的充分条件，即 $\text{dis}(x,y)$ 可以实际上不经过 $z$，不需要边分治来保障 “必须经过” 的要求。

当然，现在想想，优化建图跑最短路，不如 $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ 所说 数据结构优化转移。建出显式图，只会增加不必要的时空复杂度。非最短路问题，倒是有可能让代码实现更简单（比如 $\text{2-sat}$ 问题）。

非树边呢？相当于转移过程中，需要走过某条非树边。点分治的本质是，考虑 $\text{dis}$ 必须经过某个点；将每条非树边的任一端点设为 “特殊点”，对经过特殊点的 $\text{dis}$ 进行转移即可。

显式建图，似乎有 $\mathcal{O}(n\log n+nk)$ 条边，其中 $k=|E|?|V|+1$ 。跑 $\mathtt{d}\mathtt{i}\mathtt{j}\mathtt{k}\mathtt{s}\mathtt{t}\mathtt{r}\mathtt{a}$ 岂不是 $\mathcal{O}[n\log n\log (n\log n)]$ 了吗？可以类比此题，将 $(v_i+c_i)$ 放入 $\mathtt{h}\mathtt{e}\mathtt{a}\mathtt{p}$ 中；显式建图，则其等价于将边权为 $0$ 的连通块进行 $\mathrm{b}\mathrm{f}\mathrm{s}$ 更新。这样可以保证每个点直接得到答案，复杂度 $\mathcal{O}(n\log n+nk)$ 。

代码

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG LONG for loneliness)
#include <cctype> // DDG yydDOG & ZXY yydBUS !!!
#include <queue>
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MAXN = 200005, MAXM = 200055;
# define _go(i,x) for(int i=head[x]; ~i; i=e[i].nxt)
struct Edge{ int to, nxt; };
Edge e[MAXN<<1]; int head[MAXN], cntEdge;
void addEdge(int a, int b){
	e[cntEdge].to = b, e[cntEdge].nxt = head[a];
	head[a] = cntEdge ++;
}
const int LOGN = 18;
int siz[MAXN], dep[LOGN][MAXN], fa[MAXN][LOGN];
bool vis[MAXN]; int whole, core;
void findRoot(int x, int pre){
	siz[x] = 1; int mx = 0;
	_go(i,x) if((i^1) != pre && !vis[e[i].to]){
		findRoot(e[i].to,i), siz[x] += siz[e[i].to];
		mx = std::max(mx,siz[e[i].to]);
	}
	if((mx<<1) <= whole && whole <= (siz[x]<<1)) core = x;
}
int *group[MAXN];
int* collect(const int &level, int x, int pre, int* ptr){
	fa[x][level] = core, *(ptr ++) = x;
	_go(i,x) if((i^1) != pre && !vis[e[i].to]){
		dep[level][e[i].to] = dep[level][x]+1;
		ptr = collect(level,e[i].to,i,ptr);
	}
	return ptr;
}
void solve(int x, int level){
	static int buc[MAXN], tmp[MAXN]; ///< bucket sort
	findRoot(x,-1), memset(buc,0,whole<<2);
	dep[level][core] = 0, collect(level,core,-1,tmp);
	rep0(i,0,whole) ++ buc[dep[level][tmp[i]]];
	rep0(i,1,whole) buc[i] += buc[i-1];
	group[core] = new int[whole+1];
	*group[core] = core, group[core][whole] = -1;
	for(int *i=tmp+1; i!=tmp+whole; ++i){
		int &rnk = buc[dep[level][*i]-1];
		group[core][rnk ++] = *i;
	}
	vis[core] = true;
	const int _core = core;
	_go(i,core) if(!vis[e[i].to]){
		if(siz[e[i].to] > siz[_core])
			whole = siz[x]-siz[_core];
		else whole = siz[e[i].to];
		solve(e[i].to,level+1);
	}
}

void bfs(int *que, int *dis, int x, const int &n){
	memset(dis+1,-1,n<<2), dis[x] = 0;
	int *bac = que; *bac = x;
	for(; que!=bac+1; ++que) // keep releasing
		_go(i,x=*que) if(!(~dis[e[i].to])){
			dis[e[i].to] = dis[x]+1;
			++ bac, *bac = e[i].to;
		}
}

namespace UFS{
	int fa[MAXN];
	int find(int a);
	bool merge(int a, int b);
}
bool bad[MAXN]; int tot;
const int MAXK = 102;
int dis[MAXK][MAXN], que[MAXK][MAXN];
int *que_ptr[MAXK];

typedef std::pair<llong,int> PII;
llong ans[MAXN]; extern bool vis[MAXN];
std::priority_queue<PII> pq;
int radius[MAXN], cost[MAXN];
int main(){
	int n = readint(), m = readint();
	rep(i,1,n) UFS::fa[i] = i;
	memset(head+1,-1,n<<2);
	std::queue< std::pair<int,int> > bad_edge;
	for(int i=1,a,b; i<=m; ++i){
		a = readint(), b = readint();
		if(UFS::merge(a,b))
			addEdge(a,b), addEdge(b,a);
		else{
			bad[a] = bad[b] = true;
			bad_edge.push(std::make_pair(a,b));
		}
	}
	whole = n, solve(1,0); memset(vis+1,false,n);
	for(; !bad_edge.empty(); bad_edge.pop()){
		const std::pair<int,int> &p = bad_edge.front();
		addEdge(p.first,p.second), addEdge(p.second,p.first);
	}
	rep(i,1,n) if(bad[i]) bfs(que[tot],dis[tot],i,n), ++ tot;
	rep0(i,0,tot) que_ptr[i] = que[i];
	rep(i,1,n){
		radius[i] = readint();
		cost[i] = -readint(); // negated
	}
	ans[1] = 0, vis[1] = true;
	pq.push(PII{cost[1],1});
	while(!pq.empty()){
		int x = pq.top().second; pq.pop();
		rep0(j,0,LOGN) if(fa[x][j]) // exist
			for(int* &i=group[fa[x][j]]; ~(*i); ++i){
				if(dep[j][*i]+dep[j][x] > radius[x]) break;
				if(vis[*i]) continue; // updated
				ans[*i] = ans[x]+cost[x], vis[*i] = true;
				pq.push(PII{ans[*i]+cost[*i],*i});
			}
		rep0(j,0,tot) for(int* &i=que_ptr[j]; i!=que[j]+n; ++i){
			if(dis[j][*i]+dis[j][x] > radius[x]) break;
			if(vis[*i]) continue; // updated
			ans[*i] = ans[x]+cost[x], vis[*i] = true;
			pq.push(PII{ans[*i]+cost[*i],*i});
		}
	}
	rep(i,2,n) printf("%lld\n",-ans[i]);
	return 0;
}

int UFS::find(int a){
	if(a == fa[a]) return a;
	return fa[a] = find(fa[a]);
}
bool UFS::merge(int a, int b){
	if(find(a) == find(b)) return false;
	fa[fa[a]] = fa[b]; return true;
}