http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1785

/*
    题意：一棵n个节点的树，每个中间节点最多能让K对叶子通话。每条边最多允许一个通话
           现问最多能使多少对叶子通话
    tree dp
    in[u]表示u及其子树最多能通话的对数
    out[u]表示u及其子树最多能通话的对数，但还有一个叶子待通过u的父边连到其他叶子的（该叶子不计入）

    可通过背包算出dp[k]，占用u的k条线路（指到儿子的边）的最多对数
    然后选用k条更新in[u],out[u]
    k偶数，表明有k/2对在通话
    k奇数，表明有k/2对在通话，而且有一条待连到父边的

    n<=10^5  递归会爆 需要非递归dfs   用vector会超时

*/
#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>

using namespace std;

const int MAXN = 100010;

struct State
{
    int u,p;
    bool flag;
    State(int u,int p,bool flag):u(u),p(p),flag(flag){}
};

struct Node
{
    int v;
    Node *next;
}nodes[MAXN*2],*G[MAXN],*pE;

int N,K;
int in[MAXN],out[MAXN];
int Son[MAXN];

void add(int u,int v)
{
    pE->v=v;
    pE->next=G[u];
    G[u]=pE;
    Son[u]++;
    pE++;
}
void dfs(int u,int p)
{
    stack<State>S;
    S.push(State(u,p,0));
    while(!S.empty())
    {
        State top = S.top();S.pop();
        int u=top.u,p=top.p;
        if(top.flag)
        {
            int size=Son[u];
            int bound=min(size,2*K);
            int dp[30];
            memset(dp,-1,sizeof(dp));
            dp[0]=0;
            in[u]=0;
            out[u]=0;
            for(Node *pe=G[u];pe;pe=pe->next)
            {
                int v=pe->v;
                if(v==p)continue;
                for(int j=bound;j>=0;j--)
                {
                    if(dp[j]!=-1)
                        dp[j]+=in[v];
                    if(j&&dp[j-1]!=-1)
                        dp[j]=max(dp[j],dp[j-1]+out[v]);
                }
            }
            for(int k=0;k<=bound;k++)
            {
                if(dp[k]==-1)continue;
                if(k&1)
                    out[u]=max(out[u],dp[k]+k/2);
                else 
                    in[u]=max(in[u],dp[k]+k/2);
            }
        }
        else
        {
            S.push(State(u,p,1));
            for(Node *pe=G[u];pe;pe=pe->next)
            {
                int v=pe->v;
                if(v==p)continue;
                S.push(State(v,u,0));
            }
        }
    }
}

int main()
{
//    freopen("in","r",stdin);
    int a,b;
    while(~scanf("%d%d",&N,&K))
    {
        for(int i=1;i<=N;i++)
        {
            G[i]=0;
            Son[i]=0;
        }
        pE=nodes;
        for(int i=1;i<N;i++)
        {        
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        int root=-1;
        for(int i=1;i<=N;i++)
            if(Son[i]!=1){root=i;break;}
        if(root!=-1)
        {
            dfs(root,0);
            printf("%d\n",in[root]);
        }
        else printf("%d\n",1);
    }
    return 0;
}


edward_mj 有更好的做法，不用dp，计算一下
直接用一个rest数组记录剩下多少个需要用连向父亲这条边来解决。
http://hi.baidu.com/edwardmj/blog/item/356c542d2e3e35351f30893d.html