2014
03-09

# Treeland Exhibition

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.

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.

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.

3 1
0 1
1 2
4 1
0 1
1 2
2 3
0 0

1
2

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

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

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

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]要小，就更新。

#pragma comment(linker,"/STACK:1000000000,1000000000")//猥琐了一下
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define min(a,b) a>b?b:a
const int maxn = 10010;
const int INF = 1000000000;
int dp[maxn][110];
int sum[maxn],sumd[maxn];
struct Edge{
int v,next;
}edge[2*maxn];int N,L,E;
{
edge[E].v=b;
}
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);
{
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];
{
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;
{
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;
{
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;
for(i=0;i<N-1;i++)
{
scanf("%d%d",&a,&b);
}
dfs(0,0);
solve(0,0);
printf("%d\n",*min_element(ans,ans+N));
}
return 0;
}

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1