首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

清北学堂模拟赛d3t6 c

分析:比较神奇的一道题.要把树变成环肯定要先变成链,然后把链给拼接成环.接下来考虑一个脑洞大开的树形dp:设f[i][0]表示i不与父节点相连的链数,f[i][1]表示i与父节点相连的链数,先考虑怎么转移f[i][0],如果i不与父节点相连,那么i肯定与两个子节点相连,其它的子节点都不与父节点相连,而且要剪掉与父亲节点的一条边,所以f[i][0] = (Σf[j][0]) – f[p][0] – f[q][0] + f[p][1] + f[q][1] – 1.f[i][1]也能很容易推导出来f[i][1] = (Σf[j][0]) – f[p][0] + f[p][1].这两个式子中的p,q使我们选出来与i组成链的子节点,为了使得f[i][0/1]最小,我们要选出使f[j][1] – f[j][0]最小的p,q,这个在枚举的时候扫一下就可以了.

01
领券