Massive Algorithms: HDU 3245-Treeland Exhibition (Tree DP)

Problem Description

There are n towns in the treeland – they form a tree, as you may guess, i.e. there is a unique path between every pair of towns. The length of road connecting every pair of adjacent towns is always 1 unit.

You want to hold an exhibition simultaneously on no more than L+1 consecutive towns, i.e. you choose two towns u and v of no more than L unit apart, and set up your exhibition in all the towns on the unique path from u to v. You want to attract people from all over the treeland to your exhibition, so you’d like to minimize the sum of “travelling distance” from every town. The “travelling distance” of a town is the distance from that town to its closest exhibition-town.

Input

There are at most 25 test cases. Each case begins with two integers, n and L (n <= 10000, 0 < L <= 100), the number of towns, and the maximal distance of the “endpoint towns” you choose. Next n-1 lines contain the descriptions of connections, each with two integers a and b, indicating that town a and town b are directly connected (towns are numbered from 0 to n-1). The input ends with n = L = 0.

Output

For each test case, print the minimal sum of travelling distance.

Sample Input

Sample Output

1
2

hdu 3245 zoj zju 3188 树形DP

首先明确一点，由于是两点之间的一条路径，所以不可能出现下面的情况

即不可能出现三叉路口，出现三叉的就不是两点间的路径了

所以只能是下面两种情况

1、以u为根时，路径分布在u的两棵子树中，一棵子树中的长度为a，另一棵为

b=L-2-a,（图中红色的路径部分除外）

2、只延伸出一条路径到一棵子树中

所以在v这棵子树中有L-1长度的路径存在。

我们先假设整棵树以0为根

Dp[u][i]表示以u为根的子树中路径长度为i时的最小代价，u为路径上的一个点，且为端点。所以以0为根时的状态转移方程为

Dp[u][i]=min(dp[u][i],dp[v][i-1]+sumw[u]-sumw[v]-sum[v]);

sum[u]表示u所在的子树总的点的个数，sumw[u]表示u所在的子树中每个点到u的距离之和，sumw[u]-sumw[v]-sum[v]表示在u的子树中，去掉v所在的子树之后其他子树的点到u的距离之和，因为u为端点，所以其他子树（去除v之后的子树）到路径上的最近点都是u这一点。

所以

dp[v][i-1]+sumw[u]-sumw[v]-sum[v]代表的是分配给v这棵子树i-1长度的路径,u->v相连时的代价，如果这个代价比原先dp[u][i]要小，就更新。

子树有两种选择，取或不取，相当于01背包中每件物品的取或不取。

当然每个节点都有可能为整棵树的根，所以上面的过程只是求出了以0为根时的最少代价ans[0],0在路径上，

所以接下来以每个点（u）为根求这个点为路径上的一点时的最小代价，记为ans[u]。

对于每个点为根时的情况，就是我开头画的2、3两张图中情况了

第二步中，还是利用sumw[u]-sumw[v]-sum[v]（u为根）把v这棵子树去掉，即有一部分路径在v子树中，再加上个dp[v][a]就表示分配给v子树长度为a的路径时最小代价，即sumw[u]+ dp[v][a]-sumw[v]-sum[v],所以dp[v][a]-sumw[v]-sum[v]越小越好，所以可以增加一个tmp[a]数组记录在u的某个子树中最多分配a长度的路径时dp[v][a]-sumw[v]-sum[v]的最小值，并随时更新。

const int maxn = 10010;
const int INF = 1000000000;
int dp[maxn][110];
int sum[maxn],sumd[maxn];
int head[maxn];
struct Edge{
    int v,next;
}edge[2*maxn];int N,L,E;
void add_edge(int a,int b)
{
    edge[E].v=b;
    edge[E].next=head[a];
    head[a]=E++;
}
void dfs(int u,int fa)
{
    int i,j,k,v;
    sum[u]=1;sumd[u]=0;
    fill(dp[u],dp[u]+L+1,INF);
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        dfs(v,u);
        sumd[u]+=sumd[v]+sum[v];
        sum[u]+=sum[v];
    }
    dp[u][0]=sumd[u];
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        for(j=1;j<=L;j++)
            dp[u][j]=min(dp[u][j],dp[v][j-1]+sumd[u]-sumd[v]-sum[v]);
    }
}
int ans[maxn];
void solve(int u,int fa)
{
    int i,a,v;
    if(u==0) ans[u]=sumd[0];
    else ans[u]=N-sum[u]+sumd[fa]-sum[u];
    int tmp[110];
    fill(tmp,tmp+L+1,INF); 
    int mi=INF;
    for( i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        for( a=0;a<=L-2;a++)
            mi=min(mi,tmp[L-2-a]+dp[v][a]-sumd[v]-sum[v]);
        for( a=0;a<=L-1;a++)
        {
            tmp[a]=min(tmp[a],dp[v][a]-sumd[v]-sum[v]);
            if(a) tmp[a]=min(tmp[a],tmp[a-1]);//最多分配a,如果tmp[a-1]更优，就等于tmp[a-1]
        }
    }
    mi=min(mi,tmp[L-1]);
    sumd[u]=ans[u];
    ans[u]+=mi;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(v==fa) continue;
        solve(v,u);
    }
}
int main()
{
    int i,j,k,a,b;
    while(scanf("%d%d",&N,&L),(N||L))
    {
        if(N==1) {puts("0");continue;}
        E=0;
        memset(head,-1,sizeof(head));
        for(i=0;i<N-1;i++)
        {
            scanf("%d%d",&a,&b);
            add_edge(a,b);
            add_edge(b,a);
        }
        dfs(0,0);
        solve(0,0);
        printf("%d\n",*min_element(ans,ans+N));
    }
    return 0;
}

HDU 3245-Treeland Exhibition (Tree DP)

Labels

Popular Posts