*[topcoder]TheTree

时间:2022-04-23 09:53:40

http://community.topcoder.com/stat?c=problem_statement&pm=12746&rd=15703

这道题有意思。给了树的根和每层节点的个数,求树的直径。做法是如果该层有两个节点,那么可能是有上有下,直径加二;如果该层只有一个节点,那么从这层开始,往下都只能加一。同时,该直径不一定经过根。

#include <vector>
using namespace std; class TheTree {
public:
int maximumDiameter(vector <int> cnt);
}; int TheTree::maximumDiameter(vector <int> cnt) {
int D = cnt.size();
int ans = 0;
for (int i = 0; i < D; i++) {
int res = 0;
int flag = false;
for (int j = i; j < D; j++) {
if (cnt[j] == 1)
flag = true;
res += (flag ? 1 : 2);
ans = max(res, ans);
}
}
return ans;
};