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

/*
    題意：一棵n個節(jié)點的樹，每個中間節(jié)點最多能讓K對葉子通話。每條邊最多允許一個通話
           現(xiàn)問最多能使多少對葉子通話
    tree dp
    in[u]表示u及其子樹最多能通話的對數(shù)
    out[u]表示u及其子樹最多能通話的對數(shù)，但還有一個葉子待通過u的父邊連到其他葉子的（該葉子不計入）

    可通過背包算出dp[k]，占用u的k條線路（指到兒子的邊）的最多對數(shù)
    然后選用k條更新in[u],out[u]
    k偶數(shù)，表明有k/2對在通話
    k奇數(shù)，表明有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數(shù)組記錄剩下多少個需要用連向父親這條邊來解決。
http://hi.baidu.com/edwardmj/blog/item/356c542d2e3e35351f30893d.html