P9481 (NOI2023 d2t1) 题解

· · 题解

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;
}