自动搬运

查看原文

来自洛谷，原作者为

	StarLbright40 踏遍每一座山岳

搬运于2025-08-24 22:48:45，当前版本为作者最后更新于2023-07-30 21:51:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Dijkstra 什么的看不懂啦（

贡献一个 1kb 精品解法。

对于本题，显然有 $dep_u=\log_2u$，$siz_u=2^{n-dep_u}-1$。

由于本题没有横叉边，所以每对 $u\to v$ 显然可以拆成 $u\to\text{lca}(u,v)\to v$ 计算。

对于 $u\to\text{lca}(u,v)$ 的部分，由于第二类边均为前向边，于是此时若经过第二类边则路径一定形成环，而边权均为正，所以此时一定劣。由此这部分一定只会经过第一类边也即树边，从而这是平凡的。

接下来我们处理 $\text{lca}(u,v)\to v$ 的部分。

定义 $f_{u,i}$ 表示从点 $u$ 的满足 $dep_v=i$ 的祖先 $v$ 到 $u$ 的最短路。

首先考虑仅经过一条第二类边的情形。对于一条 $u\to v$ 的第二类边，它可以更新所有祖孙关系形如 $u\to x\to y\to v$ 的 $f_{y,dep_x}$。

再拓展到所有情形，发现这一过程与 Floyd 类似。从而枚举中转点同时注意使用恰当的枚举顺序即可。

时间复杂度为 $\mathcal O(n^2(m+2^n))=\mathcal O(n^22^n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=18,mod=998244353;const long long inf=1e18;
int n,m,a[1<<N],ans;long long dis[1<<N],sum[1<<N],f[1<<N][N];
int siz(int x){return (1<<(n-__lg(x)))-1;}
long long val(int x){return sum[x]+1ll*siz(x)*a[x];}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m;
	for(int i=2;i<1<<n;++i)
		cin>>a[i],dis[i]=dis[i>>1]+a[i];
	for(int i=(1<<n)-1;i>1;--i)
		sum[i>>1]+=val(i);
	memset(f,63,sizeof(f));
	for(int u,v,w;m--;){
		cin>>u>>v>>w;
		for(int y=v;y>u;y>>=1) for(int x=y>>1;x>=u;x>>=1)
			f[y][__lg(x)]=min(f[y][__lg(x)],w+dis[v]-dis[y]+dis[x]-dis[u]);
	}
	for(int u=1;u<1<<n;++u)
		for(int i=__lg(u)-1,v=u>>1;v;--i,v>>=1) for(int j=i-1;~j;--j)
			f[u][j]=min(f[u][j],f[u][i]+f[v][j]);
	for(int u=(1<<n)-1;u;--u){
		ans=(ans+sum[u])%mod;
		for(int i=__lg(u)-1,v=u;v>1;--i,v>>=1) if(f[u][i]<inf)
			ans=(ans+f[u][i]%mod*(siz(v)+1)+val(v^1))%mod;
	}
	cout<<ans;
	return 0;
}