题目概述

有一棵带边权的树，现在要从根节点出发，至少经过所有边一次，可以传送 $K$ 次，代价为 $C$ 。问走回根节点经过的最小边权和。

解题报告

先考虑把传送换成另一个问题，经过一条路径并走回来的代价是 $2\sum w$ ，如果走过去然后传送回来就是 $\sum w+C$ ，那么问题转化为：假装每条边都走了两次，现在要选出最多 $K$ 条不相交的路径满足 $\sum w+C-2\sum w=C-\sum w$ 最小。

这就可以树形DP做了，定义 $f_{i,j,0/1}$ 表示目前到了 $i$ ，有 $j$ 条路径已经确定了，$i$ 是否在当前待确定的路径上的最优解，然后就是背包+各种讨论。

示例程序

本地过了，BZOJ上又TLE了……

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2000;

int n,K,C,si[maxn+5],INF,f[maxn+5][maxn+5][2],g[maxn+5][2],ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5],w[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
void DP(int x,int pre=0,int sum=0){bool fst=true;
    for (int j=(si[x]=1,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre){
            DP(son[j],x,w[j]),si[x]+=si[son[j]];
            if (fst){
                for (int k=0;k<=si[son[j]];k++){
                    f[x][k][0]=min(f[x][k][0],f[son[j]][k][0]);
                    f[x][k][1]=min(f[x][k][1],f[son[j]][k][1]);
                    if (k+1<=K) f[x][k+1][0]=min(f[x][k+1][0],f[son[j]][k][1]);
                }fst=false;continue;
            }memset(g,63,sizeof(g));
            for (int i=0;i<=si[x];i++){
                int now=f[x][i][0],MAX=min(K-i,si[son[j]]);
                if (now<INF){
                    for (int k=0;k<=MAX;k++){
                        g[i+k][0]=min(g[i+k][0],now+f[son[j]][k][0]);
                        g[i+k][1]=min(g[i+k][1],now+f[son[j]][k][1]);
                        if (i+k+1<=K) g[i+k+1][0]=min(g[i+k+1][0],now+f[son[j]][k][1]);
                    }
                }now=f[x][i][1];MAX=min(K-i,si[son[j]]);
                if (now<INF){
                    for (int k=0;k<=MAX;k++){
                        g[i+k][1]=min(g[i+k][1],now+f[son[j]][k][0]);
                        if (i+k+1<=K)
                            g[i+k+1][0]=min(g[i+k+1][0],now+f[son[j]][k][1]-C),
                            g[i+k+1][1]=min(g[i+k+1][1],now+f[son[j]][k][1]);
                    }
                }
            }for (int k=0;k<=K;k++) f[x][k][0]=g[k][0],f[x][k][1]=g[k][1];
        }
    if (fst) {f[x][0][0]=sum<<1;f[x][0][1]=C+sum;return;}
    for (int k=0;k<=K;k++) f[x][k][1]=min(f[x][k][1],f[x][k][0]+C);
    for (int k=0;k<=K;k++) for (int j=0;j<2;j++) f[x][k][j]+=(2-j)*sum;
}
int main(){
    freopen("mzz.in","r",stdin);freopen("mzz.out","w",stdout);
    while (~readi(n)){
        readi(K);readi(C);E=0;memset(lnk,0,sizeof(lnk));memset(f,63,sizeof(f));INF=f[0][0][0];
        for (int i=1,x,y,z;i<n;i++) readi(x),readi(y),readi(z),x++,y++,Add(x,y,z),Add(y,x,z);
        DP(1);ans=INF;for (int i=0;i<=K;i++) ans=min(ans,f[1][i][0]);printf("%d\n",ans);
    }return 0;
}