题目

传送门= ̄ω ̄=//这题还是我贡献给LUOGU的呢!

题目描述

小 Q 正在设计一种棋类游戏。

在小 Q 设计的游戏中,棋子可以放在棋盘上的格点中。某些格点之间有连线,棋子只能在有连线的格点之间移动。整个棋盘上共有 V 个格点,编号为0,1,2 … , V− 1,它们是连通的,也就是说棋子从任意格点出发,总能到达所有的格点。小 Q 在设计棋盘时,还保证棋子从一个格点移动到另外任一格点的路径是唯一的。

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

输入输出格式

输入格式:

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

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

输出格式:

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

输入输出样例

输入样例#1:

输出样例#1:

输入样例#2:

输出样例#2:

说明

【输入输出样例 1 说明】

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

【输入输出样例 2 说明】

一种可行的移动路径为 0 → 1 → 3 → 5 → 3 → 7,经过 0, 1, 3, 5, 7 这 5 个格点。

【数据规模与约定】

对于 100%的测试点,N,V ≤ 100, 0 ≤a_i,b_i< V

题解

//我的第一个树型dp?(可能以前打过树型dp然而我并不知道那是树型dp)
很明显是棵树!
暴力不能过!
所以树型dp(然而很奇怪,贪心可以AC!那俩位打贪心の神犇说可以证明,然而我不会!)。

首先我们得知道这个东西:
对于一个节点,我们选中一个它的儿子节点。对于这种选法,我们有三种走的方法:
1. 向儿子节点的方向一条路走到黑,不返回到当前节点。
2. 向儿子节点的方向走一圈回来。
3. 向儿子节点的方向走一圈回来且再向另一个方向一条路走到黑,不会来。

简要地说就是:
1. ↙
2. ⟲
3. ⟲↘

走法1和2不会返回到当前节点,当然也就没法回到当前节点的父亲节点。
所以我们分两个数组存状态:
$f0[i][j]$表示当前到了节点$i$,还可以走$j$步时不需要回到节点$i$时最多可以访问的节点数。
$f1[i][j]$表示当前到了节点$i$,还可以走$j$步时需要回到节点$i$时最多可以访问的节点数。

具体:
对于$dfs(u)$,我们枚举子节点为i,再从n(最多可以走的步数)到1枚举当前剩余步数为j,再从1到j枚举下一步的剩余步数k。
对于走法1,需要满足$j-k>0$,然后:$f[0][u][j]=max(f[0][u][j],f[0][i][k]+f[1][u][j-k-1])$
对于走法2,需要满足$j-k>=2$,然后:$f[1][u][j]=max(f[1][u][j],f[1][
i][k]+f[1][u][j-k-2])$
对于走法3,需要满足$j-k>=2$,然后:$f[0][u][j]=max(f[0][u][j],f[1][*i][k]+f[0][u][j-k-2])$

为什么走法1和走法2要加一个$f[1][u][j-k-1]$或$f[1][u][j-k-2]$呢?
因为我们可以先从别的地方绕一圈回来,再执行走法1、走法2。

还有,枚举j的时候一定要从大到小,原因就像01背包,要从大的到小的更新,不然状态之间会互相影响,然后wa(考试的时候脑子抽了就写错了这里,掉了50分)。

其他具体看代码吧!