专栏文章

题解：P11492 [BalticOI 2023] Minequake

BBaiBaiShaFeng
P11492题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minna937
此快照首次捕获于
2025/12/02 05:12
3 个月前
此快照最后确认于
2025/12/02 05:12
3 个月前
查看原文
没有题解？没有评级？我写一篇。
我们在手玩样例的时候会发现每次从儿子到父亲就像是把整个儿子的子树中所有的值加上一个前置的时间，最后合并道子树上边。
合并子树信息类型的题目，考虑上树形 dp。
但是我们合并只能往根，加上一个换根 dp 就好，看下数据范围是 O(n)O(n) 或者 O(nlog⁡n)O(n\log n)，姑且认为这个思路值得一试。
先设 f[u]f[u] 表示 uu 的子树中从 uu 出发，到各个点第一次时间的最小值，这个时候 f[root]f[root] 就是我们从根节点出发的答案了，换根 dp 的标准套路。
我们不难想出来这么一个转移方程：f[u]=∑v∈son[u]f[v]+siz[v]×(2×siz[u]−1)f[u]=\sum_{v\in son[u]} f[v] + siz[v] \times (2 \times siz[u] - 1)。
这个 siz[u]siz[u] 就是正常的子树大小，和 f[u]f[u] 同时更新，也就是 siz[u]siz[u] 在计算完 dp[v]dp[v] 后回立刻更新。
并不难理解，相当于累加了前置所需的时间。
这个时候有的人就要问了，BaiBaiShaFeng 你这个东西的转移明明是依靠顺序的啊，凭什么这个就是对的。
其实这个东西不依靠任何的顺序，如果你用 viv_i 表示第 ii 个儿子，之后将 siz[u]siz[u] 拆成 ii 之前的儿子的子树大小和，再进行拆式子，你会发现这个东西确确实实不论顺序，最后的总和是一样的。
然后我们考虑怎么换根。
我们设 dp[u]dp[u] 表示以 uu 为根的答案，vv 是它的子节点。
dp[v]=dp[u]−(n−siz[v])+siz[v]dp[v]=dp[u]-(n-siz[v])+siz[v]。
然后就没有了。
代码如下。
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
struct Node{
    int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){
    node[++tottt].to=v;
    node[tottt].nxt=head[u];
    head[u]=tottt; return;
}
int n, f[MN], dp[MN], siz[MN], ans;
void dfs1(int u, int father){
    siz[u]=1;
    for(int i=head[u];i;i=node[i].nxt){
        int v=node[i].to;
        if(v==father) continue;
        dfs1(v,u);
        f[u]+=f[v]+siz[v]*(2*siz[u]-1);
        siz[u]+=siz[v];
    }
}
void dfs2(int u, int father){
    for(int i=head[u];i;i=node[i].nxt){
        int v=node[i].to;
        if(v==father) continue;
        dp[v]=dp[u]-n+2*siz[v]; ans=min(dp[v],ans);
        dfs2(v,u);
    }
}
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1; i<n; ++i){
        int u, v; cin>>u>>v;
        insert(u,v); insert(v,u);
    }
    dfs1(1,0); ans=dp[1]=f[1];
    dfs2(1,0); cout<<ans<<'\n';
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...