HBC232740环球旅行,数据结构,树,动态规划,树形dp净题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

如果你厌倦了长文题意，可以参考下面的伪代码理解题意。 你有一个数组 fa[i]fa[i]fa[i] 表示结点 iii 的父亲结点编号，初始 fa[2]=fa[3]=1fa[2]=fa[3]=1fa[2]=fa[3]=1；另有一个数组 tp[i]tp[i]tp[i] 表示结点 iii 的属性（左孩子结点还是右孩子结点）。初始 tp[2]=′L′tp[2]=tt{'L'}tp[2]=′L′，tp[3]=′R′tp[3]=tt{'R'}tp[3]=′R′。 即初始的树如右图所示： 接下来给出一个操作序列 strstrstr，其中会包含三种字符 L, R, Mtt L,~R,~ML, R, M： Ltt LL 操作：对所有上一轮新生成的结点中（初始新生成的结点是 2,32,32,3）所有 tp[i]=′L′tp[i]=tt{'L'}tp[i]=′L′（左孩子）的结点，生成两个孩子结点，一个左孩子一个右孩子。 Rtt RR 操作：对所有上一轮新生成的结点中（初始新生成的结点是 2,32,32,3）所有 tp[i]=′R′tp[i]=tt{'R'}tp[i]=′R′ （右孩子）的结点，生成两个孩子结点，一个左孩子一个右孩子。 Mtt MM 操作：对所有上一轮新生成的结点中（初始新生成的结点是 2,32,32,3）所有的结点（不论属性），生成两个孩子结点，一个左孩子一个右孩子。 最终求执行完 kkk 次操作序列 strstrstr 后（可以理解成将序列 strstrstr 复制成原来的 kkk 倍并依次执行）树的直径长度（树上一条链包含最多的结点个数）是多少。 如果你厌倦了长文题意，可以参考下面的伪代码理解题意： 代码中 Tree_Diametre(fa)rm Tree_Diametre(fa)Tree_Diametre(fa) 表示利用 farm fafa 数组求树的直径。

全网最全C++题库，助您挑战自我，突破极限，成为编程领域的佼佼者！

标签： HBC232740环球旅行 数据结构 树 动态规划 树形dp净题解