XSY 2176 - tree

题目精选 树形dp 序的应用

---

题意

分析

  给定 $k$ 个点 $A_1,A_2,...,A_k$ ，定义 $A_0=A_k$ ，它的树链的并的值就是

$$sum=\frac{(\sum_{i=0}^{n-1} dist(A_i,A_{i+1}))}{2}$$
  回到本题，我们所求就是 $树链的并\times 2-最长链$ 的最小值。

  我们考虑进行树形dp。
$f[i][j]$ ：在以 $i$ 为根的子树中，选了 $j$ 个点，子树内有 $0$ 条出现次数为 $1$ 的路径 的最小值。
$g[i][j]$ ：在以 $i$ 为根的子树中，选了 $j$ 个点，子树内有 $1$ 条出现次数为 $1$ 的路径，且路径的终点为根 的最小值。
$h[i][j]$ ：在以 $i$ 为根的子树中，选了 $j$ 个点，子树内有 $2$ 条出现次数为 $1$ 的路径 的最小值。

  dp的方法很容易，这里不赘述。

实现

#include <cstdio>
#include <iostream>
#include <cctype>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (register int i=(a);i<=(b);i++)
#define D(i,a,b) for (register int i=(a);i>=(b);i--)
const int N=3005;
const int E=6005;
const int INF=~0u>>2;
int n,nk;
struct Ed {
    int v,d,nx;
    inline Ed(int _v=0,int _d=0,int _nx=0):v(_v),d(_d),nx(_nx){}
}mp[E];
int tot,hd[N];
int siz[N];
int f[N*N];
int g[N*N];
int h[N*N];
int ans;
inline int rd(void) {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
inline void Ins(int u,int v,int d) {
    mp[++tot]=Ed(v,d,hd[u]); hd[u]=tot;
    mp[++tot]=Ed(u,d,hd[v]); hd[v]=tot;
}
inline void gmin(int &x,int y) {
    x=min(x,y);
}
inline int id(int i,int j) {
    return (i-1)*n+j;
}
void DP(int x,int pre) {
    int t=1;
    for (int k=hd[x];k>0;k=mp[k].nx)
        if (mp[k].v!=pre) {
            DP(mp[k].v,x);
            t+=siz[mp[k].v];
        }
    siz[x]=1;
    f[id(x,1)]=g[id(x,1)]=h[id(x,1)]=0;
    F(i,2,t) f[id(x,i)]=g[id(x,i)]=h[id(x,i)]=INF;
    for (int k=hd[x];k>0;k=mp[k].nx)
        if (mp[k].v!=pre) {
            int son=mp[k].v,d=mp[k].d;
            D(i,siz[x],1) F(j,1,siz[son]) {
                gmin(f[id(x,i+j)],f[id(x,i)]+f[id(son,j)]+2*d);
                gmin(g[id(x,i+j)],g[id(x,i)]+f[id(son,j)]+2*d);
                gmin(g[id(x,i+j)],f[id(x,i)]+g[id(son,j)]+d);
                gmin(h[id(x,i+j)],h[id(x,i)]+f[id(son,j)]+2*d);
                gmin(h[id(x,i+j)],g[id(x,i)]+g[id(son,j)]+d);
                gmin(h[id(x,i+j)],f[id(x,i)]+h[id(son,j)]+2*d);
            }
            siz[x]+=siz[son];
        }
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    cin>>n>>nk;
    F(i,1,n-1) {
        int x=rd(),y=rd(),d=rd();
        Ins(x,y,d);
    }
    DP(1,-1);
    ans=INF; F(i,1,n) if (siz[i]>=nk) gmin(ans,h[id(i,nk)]); cout<<ans<<endl;
    return 0;
}