三金老师

分类

题解(25)

/ 注册

全部文章（共3篇）

【每日一题】Treepath(树形dp)

Solution记得寒假牛客有道题就是这道题的扩展，好像是求路径数目+博弈论。表示以 i 为根的子树到 i 的距离为偶数/奇数的数目。那么在dfs过程中，以 u 为根且子结点为 v 对答案的贡献是: (子结点与父节点距离相差1，所以应操作不同奇偶性)当然遍历完也需要把 v 的路径数合并到 u里...

每日一题树形DP 思维

2020-04-15

0 736

【每日一题】Shortest Path (dfs+思维)

Solutionn个点n-1条双向边明显是树，而且保证必定是偶数个节点，那么就肯定是两两配对。就一个节点来说，跟兄弟节点配对，或者跟父亲节点配对肯定是最优的。所以只需要判断节点所在子树里面的节点数是否为偶数，如果是偶数说明不用和此节点的父亲节点配对，若为奇数则需要加上这条边，那么可设 dp[i] 为...

每日一题树形DP

2020-04-02

1 754

【每日一题】Rinne Loves Edges (树形DP)

Solution简单来说题目就是求在有根树中，每个叶子节点到根节点的路径上的边权最小值之和，很典型的树形DP。s为根，考虑 dp[s] 为答案，即每个叶子节点到s的路径上的边权最小值之和，那么 dp[s]= Σ min（dp[s.son] , s->s.son的边权) 。最后注意一下叶子节点是...

每日一题树形DP

2020-03-31

0 592