题意:
给出n个点, n-1条有向边, 问从一个点出发到其他所有点时, 使得逆的边数最小的出发点, 以及逆的边数. 有多个出发点的话升序输出.
思路:
树形DP.
这里DP的要义是一种递推, 只不过是沿着树的结构去递推.
有一个关系需要发现: 当知道一个点到其他所有点需要逆的边的条数之后, 其他各点的结果可以通过递推求出:
假设root有son1和son2, root到其他所有点, 都是先到son1, son2, 再接着往下走.
那么求son1到所有点的时候, son1到son1子树的计数情况和root的计数情况相同, son1到root之后再走son2子树的计数情况也和root相同. 于是只......
阅读全文