[bzoj4813][Cqoi2017]小Q的棋盘

来自FallDream的博客，未经允许，请勿转载，谢谢。

---

小Q正在设计一种棋类游戏。在小Q设计的游戏中，棋子可以放在棋盘上的格点中。某些格点之间有连线，棋子只能在有连线的格点之间移动。整个棋盘上共有V个格点，编号为0,1,2…,V-1，它们是连通的，也就是说棋子从任意格点出发，总能到达所有的格点。小Q在设计棋盘时，还保证棋子从一个格点移动到另外任一格点的路径是唯一的。小Q现在想知道，当棋子从格点0出发，移动N步最多能经过多少格点。格点可以重复经过多次，但不重复计数。n,v<=100

很明显是sb树形dp啊，但是这数据范围.....

f[0/1][i][j]第i个节点，走了j次，回不回根节点最大答案，很好转移。

我是不会告诉你们我对着这sb题猛wa了几次的

#include<iostream>

#include<cstdio>

#include<cstring>

#define MN 100

using namespace std;

int X;char ch;

inline int read()

{

    X =  , ch = getchar();

    while(ch < '' || ch > '') ch = getchar();

    while(ch >= '' && ch <= '')X = X *  + ch - '',ch = getchar();

    return X;

}

int f1[MN+][MN+],f2[MN+][MN+],cnt=,n,m,ans=,head[MN+];

struct edge{int to,next;}e[MN*+];

inline void ins(int f,int t)

{

    e[++cnt]=(edge){t,head[f]};head[f]=cnt;

    e[++cnt]=(edge){f,head[t]};head[t]=cnt;

}

void dfs(int x,int fa)

{

    f1[x][]=f2[x][]=;

    for(int i=head[x];i;i=e[i].next)

        if(e[i].to!=fa)

        {

            dfs(e[i].to,x);

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

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

                {

                    if(k<j-)f1[x][j]=max(f1[x][j],f1[e[i].to][k]+f1[x][j-k-]),

                             f2[x][j]=max(f2[x][j],f1[e[i].to][k]+f2[x][j-k-]);

                    f2[x][j]=max(f2[x][j],f2[e[i].to][k]+f1[x][j-k-]);

                }

        }

}

int main()

{

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

    for(register int i=;i<n;i++)ins(read()+,read()+);

    dfs(,);

    for(register int j=;j<=m;j++)

         ans=max(ans,f2[][j]);

    cout<<ans;

    return ;

}