web analytics

POJ 1344 Tree Size Problem 树形DP

题目链接:http://poj.org/problem?id=1344

题目大意:给你一棵树上每个叶节点的距离,然后让你求树的权值和。

分析:

既然给了距离相当于给了图。但是由于我们不知道每个叶子节点的关系。但是不用担心。我们首先得意淫一个已经完整的树。

1,在这棵由我们意淫出的完整的树上肯定有2个叶子节点在另一个节点下面。但是由于不知道是哪对节点所以我们要枚举两个点。

2,既然我们枚举出了2个点,那么我们可以完整的确定这就是两个叶子节点,所以他们两的距离是肯定要加入答案的,之后将2个点合并成一个新的点,加入这颗树,这时候我们要更新这个新点与其他的距离。

3,然后重复上两个操作直到只有一个点的时候。

Post a Comment

You must be logged in to post a comment.