Eva

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 990  Solved: 565
Description

小Q正在设计一种棋类游戏。在小Q设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能

在有连线的格点之间移动。整个棋盘上共有V个格点，编号为0,1,2…,V-1，它们是连通的，也就是说棋子从任意格

点出发，总能到达所有的格点。小Q在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

小Q现在想知道，当棋子从格点0出发，移动N步最多能经过多少格点。格点可以重复经过多次，但不重复计数。

Input

第一行包含2个正整数V,N，其中V表示格点总数，N表示移动步数。

接下来V-1行，每行两个数Ai,Bi,表示编号为Ai,Bi的两个格点之间有连线。

V,N≤ 100, 0 ≤Ai,Bi<V 

Output 

输出一行一个整数，表示最多经过的格点数量。

Sample Input

5 2
1 0
2 1
3 2
4 3

Sample Output

3
从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。

HINT 

Source 

/**************************************************************

    Problem: 4813

    User: ictsing

    Language: C++

    Result: Accepted

    Time:28 ms

    Memory:1376 kb

****************************************************************/

 

//BZOJ4813 [Cqoi2017]小Q的棋盘

#include <iostream>

#include <cstdio>

using namespace std;

const int mt = 100+5;

const int mod = 1000000000+7;

int ecnt=0;

int f[mt][mt],g[mt][mt];

int to[mt<<1],nxt[mt<<1],adj[mt<<1];

int n,m;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

      ch=getchar();

      if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

      num=num*10+ch-'0';

      ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void adde(int u,int v)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],adj[u]=ecnt;

}

void dfs(int u,int fa)

{

    for(int i=0;i<=m;i++) g[u][i]=f[u][i]=1;

    for(int i=adj[u];i;i=nxt[i])

    {

        int v=to[i];

        if(v==fa) continue;

        dfs(v,u);

        for(int j=m;j>=0;j--)

        {

            for(int k=1;k<=j;k++)

            {

                f[u][j]=max(f[u][j],f[v][k-1]+g[u][j-k]);

                if(k>=2)

                {

                    g[u][j]=max(g[u][j],g[v][k-2]+g[u][j-k]);

                    f[u][j]=max(f[u][j],g[v][k-2]+f[u][j-k]);

                }

            }

        }

    }

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=n-1;i++)

    {

        int x=read(),y=read();

        x++,y++;

        adde(x,y),adde(y,x);

    }

    dfs(1,0);

    printf("%d\n",f[1][m]);

    return 0;

}