*[topcoder]TheTree - 阿牧遥 - 博客园

*[topcoder]TheTree - 阿牧遥 - 博客园

Manao is working in the Tree Research Center. It may come as a surprise that the trees they research are not the ones you can see in a park. Instead, they are researching special graphs. (See Notes for definitions of terms related to these trees.) Manao's daily job is reconstructing trees, given some partial information about them. Today Manao faced a difficult task. He needed to find the maximum possible diameter of a tree, given the following information: Some vertex in the tree is called V. The distance between V and the farthest vertex from V is D. For each x between 1 and D, inclusive, Manao knows the number of vertices such that their distance from V is x. You are given a int[] cnt containing D strictly positive integers. For each i, the i-th element of cnt is equal to the number of vertices which have distance i+1 from V. Please help Manao with his task. Return the maximum possible diameter of a tree that matches the given information.

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

https://github.com/phungleson/topcoder/blob/master/src/main/java/phungleson/topcoder/srm591/TheTree.java


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;

};

Read full article from *[topcoder]TheTree - 阿牧遥 - 博客园