题解：P5866 [SEERC 2018] Space Station

Fire_flys · 2026-04-25 15:52:28 · 题解

这道题还是挺不错的，想了挺久没想出来看题解，结果发现题解除了 Provicy 这位大佬的题解以外，其它题解似乎都没有解释自己的转移方程的定义和转移是怎么来的（~~强烈谴责，因为我没有看懂~~）。于是在经过许久终于自己搞定以后，我决定自己写一篇题解来讲下思路。

首先我们贪心地想一下，我们每走进或瞬移进一棵子树后，不管你是否使用那个瞬移，最优肯定是把这棵子树里面的所有边全部走完再去走别的子树，因为这样可以避免一条边走两次以上。

然后题目给出来一个瞬移次数的限制，那么我们就可以往这方面去设计一个转移方程。

具体地，设 dp_{u,i} 表示已经走完 u 的子树以后，有 i 个点连了一条额外的边（也就是使用了瞬移，相当于在瞬移的两个端点连了一条长度为 k 的边）的最小花费时间。

根据前面的贪心，你在一棵子树里的某条链上使用贪心的时候，肯定不能在这条链上的中间使用那个瞬移，不然你肯定会制造出下面的有些边没有被走又去走别的链，那么肯定还有把下面的边走了才能满足题意，肯定是不优的。所以我们应该要么在某个子树的根节点用瞬移，要么在子树的叶子节点内用这个瞬移。

我们拿第二个样例的树来看一下：

比如你在 5 的子树里，想要使用瞬移，你瞬移一次，会有以下几种情况：

你瞬移出去 5 的子树，比如你在 6，瞬移到了 4，那么 5 及其子树内额外连了一条边的节点数量就会增加 1，也就是 6 连了一条额外的边。然后
你从外面瞬移到了 5 的子树内，那么跟上面同理，你子树内只有 1 个点会额外连一条边。
你从 5 的子树内的某个节点中移动到了 5 的子树内的另一个节点，那么这两个节点都会额外连一条边，额外连了一条边的节点数量就会增加 2。

结论

如果子树内额外加边的节点数是奇数的话，就代表有某个点是从另外一棵子树走进来的，或者走到了外面的子树。而如果是偶数的话，就代表是在子树内行走。

那么对于一个父子关系 (u,v)，有如下转移：

如果额外加边节点数是奇数，那么 (u,v,w) 这条边就只会走一次，因为不是从 (u,v,w) 这条边进入或走出 u 的子树，所以有：

\begin{aligned}dp_{u,i+j}=\min(dp_{u,i+j},dp_{u,i}+dp_{v,j}+w) \end{aligned}

\begin{aligned}dp_{u,i+j+1}=\min(dp_{u,i+j+1},dp_{u,i}+dp_{v,j}+w) \end{aligned}

反之，若是偶数，则表示是从 (u,v,w) 走进来的，并且是从 (u,v,w) 走出来的，那么有：

\begin{aligned}dp_{u,i+j}=\min(dp_{u,i+j},dp_{u,i}+dp_{v,j}+2\times w) \end{aligned}

\begin{aligned}dp_{u,i+j+1}=\min(dp_{u,i+j+1},dp_{u,i}+dp_{v,j}+2\times w) \end{aligned}

那么这个题就做完了。下为代码： ::::info[code]

#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
#define pii pair<int,int> 
const int N=1e3+10,inf=1e17;
vector<pii> g[N];
int dp[N][N];//dp[i][j]表示已经走完了i的子树后有j个点连了一条额外的边 
int n,m,K,siz[N],f[N];
void dfs(int u,int fa){
    siz[u]=1;
    for(pii tmp:g[u]){
        int v=tmp.first,w=tmp.second;
        if(v==fa)continue;
        dfs(v,u);
        memset(f,0x3f,sizeof f);
        for(re int i=0;i<=siz[u];i++){
            for(int j=0;j<=siz[v];j++){
                if(i+j>2*m)break;
                if(j%2==1){//奇数代表有一个点是从外面进来的 
                    f[i+j]=min(f[i+j],dp[u][i]+dp[v][j]+w);
                    f[i+j+1]=min(f[i+j+1],dp[u][i]+dp[v][j]+w);
                }
                else{//偶数代表所有的点相互配对 
                    f[i+j]=min(f[i+j],dp[u][i]+dp[v][j]+2*w);
                    f[i+j+1]=min(f[i+j+1],dp[u][i]+dp[v][j]+2*w);
                }
            }
        }
        siz[u]+=siz[v];
        for(int i=0;i<=siz[u];i++)dp[u][i]=f[i];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n>>m>>K;
        for(re int i=1;i<=n;i++)g[i].clear();
        for(re int i=1,u,v,w;i<n;i++){
            cin>>u>>v>>w;
            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }
        for(re int i=1;i<=n;i++){
            for(re int j=0;j<=2*m;j++){
                dp[i][j]=0;
            }
        }
        dfs(1,0);
        int ans=inf;
        for(re int i=0;i<=min(n,2*m);i+=2)ans=min(ans,dp[1][i]+(i/2)*K);
        cout<<ans<<"\n";
    }
    return 0;

}

::::