P9481 [NOI2023] 贸易题解

题目大意

P9481 [NOI2023] 贸易

Solution

萌萌题。

也是做上 NOI 的题了呀。

首先因为题目满二叉树的优秀性质，我们可以得到两个式子：

$dep_u=log_2 u$
$siz_u=2^{n-dep_u}-1$

不用证明吧，手推一下就出来了。

接着考虑几种 $dist(u,v)$ 的情况，分别是“子到祖”、“祖到子”、“彼到此”。说人话就是：

$u$ 是 $v$ 的祖先，考虑 $v\to u$ 的贡献（水）。
$v$ 是 $u$ 的祖先，考虑 $v\to u$ 的贡献。
$u$，$v$ 在不同的子树内，考虑 $u\to v$ 的贡献。

第一个情况好搞，这里不说了，就是无脑爬一类边。这里不会走二类边，因为权值为正，所以没必要兜圈子。

第二种情况我们设一个 $f_{u,i}$ 表示 $u$ 的深度为 $i$ 的祖先到 $u$ 的距离。

如果 $u$ 是 $v$ 的祖先且有 $u\to v$，显然转移为：

$$ f_{v,dep_u}=\min \{w_{u,v} \} $$

$w_{u,v}$ 是这条有向边的边权。

上面这个转移还是 too simple 了呀，我们接着考虑在路径 $v\to u$ 上的点 $x$ 到路径 $v\to x$ 上 $y$ 的最短路。

其实我们预处理出所有点的 $dist(1,i)$ 之后，这个显然是好转移的，相当于是兜个圈子：

$$ f_{y,dep_x}=\min \{w_{u,v}+dist(1,v)-dist(1,y)+dist(1,x)-dist(1,u) \} $$

这条链是这样的：$v\to \dots\to y\to \dots \to x\to\dots\to u\to\dots\to 1$

更新所有点的过程很像 Floyd 的过程，注意枚举顺序即可。

这样就搞定第二种情况了。

现在考虑第三种情况。

聪明的小朋友已经发现了呀，第三种情况的实现就是靠前两种情况贡献得来的。

首先在情况一时我们可以搞一个类似于前缀和的东西把该点子树内的一些计数信息都推上来到该点。

其次在情况二时我们已经得到了 $f_{u,i}$。

那么计数就很简单了，我们在考虑到点 $u$ 时，我们只需要边爬父亲，边计算该父亲另一个儿子的贡献。

具体的就是：

$$ \sum f_{u,i}\times (siz(v\oplus 1)+1)+val(v\oplus 1) $$

$u$ 是枚举的当前点，$v$ 是不断向父亲爬的点（初始为 $u$），$i$ 是 $v$ 父亲的 $dep$，$v\oplus 1$ 是 $v$ 的兄弟节点（满二叉树性质）。

就此完了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define ft first
#define sd second

const int N=18,M=262144,P=998244353,INF=1e18;

int n,m;
int dis[M],sum[M],f[M][N],a[M];

int dep(int u) { return log2(u); }

int siz(int u) { return (1<<(n-dep(u)))-1; }

int val(int u) { return sum[u]+siz(u)*a[u]; }

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=2;i<(1<<n);i++){
        scanf("%lld",&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,0x3f,sizeof(f));
    while(m--){
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        for(int y=v;y>u;y>>=1)
            for(int x=y>>1;x>=u;x>>=1)
                f[y][dep(x)]=min(f[y][dep(x)],w+dis[v]-dis[y]+dis[x]-dis[u]);
    }
    for(int u=1;u<(1<<n);u++)
        for(int i=dep(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]);
    int ans=0;
    for(int u=(1<<n)-1;u;u--){
        (ans+=sum[u])%=P;
        for(int i=dep(u)-1,v=u;v>1;i--,v>>=1){
            if(f[u][i]<INF)
                (ans+=f[u][i]*(siz(v^1)+1)%P+val(v^1))%=P;
        }
    }
    printf("%lld\n",ans);
    return 0;
}