CSP-S 2022《数据传输》解题报告

题目链接

题意

$n$台主机用$n-1$根网线连接，构成一棵树。如果两台主机在树上的距离不超过$k$，则可以直接传输数据。每台主机处理数据的时间为$v_i$。有$q$次询问，每次询问从主机$s_i$发送到主机$t_i$至少需要花费多少时间。

数据范围

$1\leq n, q \leq 2\times 10^5$

$1\leq k \leq 3$

$1\leq v_i\leq 10^9$

解题思路

对于每个查询，u，v的最短路构成一条链，加入每次传输都在这条链上，问题可以等价于在链上选一些点使得不存在连续三个点没有被选中。

接着，考虑如果传输可以跳出这条链，对于u一次跳跃如下图所示，只能跳在四个位置上，跳在其它位置一定不会获得更小成本。对于1、2位置深度相同，可以等价于跳在同一位置。

考虑倍增算法，并在倍增的过程中用动态规划维护跳上去的最小成本。

用$dp[i][j][x][y]$表示从节点$i$开始向上跳$2^j$次到$f[i][j]$，节点$i$当前可以跨越$x$个点，到达$f[i][j]$之后还可以跨越$y$个点。

按照k=3的情况，理解跨越$x,y$个点：如果在链上节点u有0个点未被标记，则u可以跨越两个点去标记下一个点，x=2；如果有1个点未被标记，则u最多也只能跨越一个点；如果有两个点未被标记，则u不能跨越任何点，只能去标记父亲。

如此可以通过$O(k^3 n\log n)$在倍增过程中计算每次倍增的最小成本。具体实现见代码，初始化过程细节非常多。

对于每次查询，跳到$lca$下面一点，再考虑最后一跳使两点重合。注意就算$v$是$u$的祖先，$u$也只能跳到$v$的下面，因为上图中1号位置、2号位置的等价存在，所以在dp转移式中不能体现这两个点具体位置，但是终点是一个具体的位置，这两个位置失去了等价关系，最后一跳需要单独转移。（就是这个地方没写对，调试了一整个下午，人都要疯了）

时间复杂度：$O(k^3n\log n + k^2q\log n)$

代码

/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/ 
************************************************************************/

#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 2e5 + 10;
int n, Q, k, f[maxx][20], dep[maxx];
LL dp[maxx][20][3][3], inf, a[maxx], mn[maxx];
vector<int> eg[maxx];
void dfs(int id, int fa){
	f[id][0] = fa;
	dep[id] = dep[fa] + 1;
	mn[id] = inf;
	for(auto u : eg[id]){
		if(u == fa) continue;
		dfs(u, id);
		mn[id] = min(mn[id], a[u]);
	}
}
void init(){
	for(int i = 1; i < 20; ++i)
		for(int j = 1; j <= n; ++j)
			f[j][i] = f[f[j][i - 1]][i - 1];
}
void pre_sol(int id){
	if(k == 3){
		dp[id][0][2][2] = dp[id][1][2][1] = mn[f[id][1]];
		dp[id][1][2][2] = dp[id][2][2][0] = a[f[id][1]];
		dp[id][2][2][1] = a[f[f[id][1]][0]];

		dp[id][0][1][2] = dp[id][1][1][1] = a[f[id][0]];
		dp[id][1][1][2] = dp[id][2][1][0] = a[f[id][1]];

		dp[id][0][0][2] = dp[id][1][0][1] = a[f[id][0]];

		dp[id][0][2][1] = dp[id][1][2][0] = 0;
		dp[id][0][1][0] = 0;
	}
	else if(k == 2){
		dp[id][0][1][1] = dp[id][1][1][0] = a[f[id][0]];
		dp[id][1][1][1] = a[f[id][1]];

		dp[id][0][0][1] = dp[id][1][0][0] = a[f[id][0]];

		dp[id][0][1][0] = 0;
	}
	else dp[id][0][0][0] = a[f[id][0]];
	for(auto u : eg[id]){
		if(u == f[id][0]) continue;
		pre_sol(u);
	}
}
void DP(){
	for(int i = 1; i < 20; ++i)
		for(int j = 1; j <= n; ++j)
			for(int x = 0; x < k; ++x)
				for(int y = 0; y < k; ++y)
					for(int z = 0; z < k; ++z)
						dp[j][i][x][y] = min(dp[j][i][x][y], dp[j][i - 1][x][z] + dp[f[j][i - 1]][i - 1][z][y]);
}
LL jump(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	LL costu[3] = {a[u], a[u], a[u]}, costv[3] = {a[v], a[v], a[v]}, tmp[3], ans = inf;
	for(int i = 19; i >= 0; --i){
		if(dep[f[u][i]] > dep[v]){
			for(int x = 0; x < k; ++x)  tmp[x] = costu[x], costu[x] = inf;
			for(int x = 0; x < k; ++x)
				for(int y = 0; y < k; ++y)
					costu[x] = min(costu[x], tmp[y] + dp[u][i][y][x]);
			u = f[u][i];
		}
	}
	if(f[u][0] == v){
		for(int i = 0; i < k; ++i) ans = min(ans, costu[i]);
		return ans + a[v];
	}
	else if(dep[u] > dep[v]){
		for(int x = 0; x < k; ++x)  tmp[x] = costu[x], costu[x] = inf;
			for(int x = 0; x < k; ++x)
				for(int y = 0; y < k; ++y)
					costu[x] = min(costu[x], tmp[y] + dp[u][0][y][x]);
		u = f[u][0];
	}
	for(int i = 19; i >= 0; --i){
		if(f[u][i] != f[v][i]){
			for(int x = 0; x < k; ++x)  tmp[x] = costu[x], costu[x] = inf;
			for(int x = 0; x < k; ++x)
				for(int y = 0; y < k; ++y)
					costu[x] = min(costu[x], tmp[y] + dp[u][i][y][x]);
			for(int x = 0; x < k; ++x)  tmp[x] = costv[x], costv[x] = inf;
			for(int x = 0; x < k; ++x)
				for(int y = 0; y < k; ++y)
					costv[x] = min(costv[x], tmp[y] + dp[v][i][y][x]);
			u = f[u][i];
			v = f[v][i];
		}
	}
	for(int x = 0; x < k; ++x)
		for(int y = 0; y < k; ++y){
			if(x + y >= k) ans = min(ans, costu[x] + costv[y]);
			else ans = min(ans, a[f[u][0]] + costu[x] + costv[y]);
			if(x >= 1 && y >= 1) ans = min(ans, a[f[u][1]] + costu[x] + costv[y]);
		}
	return ans;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt","w", stdout);
#endif
	cin >> n >> Q >> k;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	for(int i = 1; i < n; ++i){
		int u, v;
		cin >> u >> v;
		eg[u].push_back(v);
		eg[v].push_back(u);
	}
	memset(dp, 1, sizeof(dp));
	inf = dp[0][0][0][0]; a[0] = inf; mn[0] = a[1];
	dfs(1, 0);
	init();
	pre_sol(1);
	DP();
	while(Q--){
		int u, v;
		cin >> u >> v;
		cout << jump(u, v) << endl;
	}
	return 0;
}