Tag: 树形dp

2 篇文章

Luogu P1273 有线电视网 题解
Describe 题目链接 某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的,一场转播的总费用等于传输信号的费用总和。 现在每个用户都准备了一笔费用想观看这场精彩的…
Luogu P2585 [ZJOI2006]三色二叉树 题解
Describe 题目链接 Solution $0-$绿色,$1-$红色,$2-$蓝色。 设$f[i][j]$表示$i$节点染成$j$这种颜色的最大值。 如果$i$节点的没有儿子,那么很明显$f[i][0]=1$。 如果$i$节点有一个儿子,那么$f[i][0]=max(f[to][1],f[to][2])+1,f[i][1]=max(f[to][…