Problem Statement |
|||||||||||||
|
You are a genealogist specializing in family trees of vampires. Vampire family trees differ from human family trees. In particular, vampires are "born" in a different way. The only way to create a new vampire is that an existing vampire turns a living human into a new vampire. Whenever this happens, we say that the older vampire is the master and the newly created vampire is the servant of that master. Given a particular family of vampires, the distance between two vampires is the smallest number of steps along the family tree we need to make in order to get from one vampire to the other. Formally, in each step you can move from the current vampire to any of its servants, or to its master (if it has one). Note that for each vampire V the distance between V and V is zero. You are now studying one particular family of vampires. These vampires have all been created from a single vampire: the True Ancestor. This special vampire has no master. You know that there are n vampires in the family, and you have numbered them 0 through n-1 (in no particular order). You do not know the master/servant relationships between the vampires in the family. The only information you have is a vector <int> num with n elements. For each valid i, the following statement is true: "If vampire i is the True Ancestor, he has exactly num[i] servants. Otherwise, he has exactly (num[i] - 1) servants." Consider all valid family trees that are consistent with this information. If there are no such trees, return -1. Otherwise, find and return the maximum distance between any two vampires in any of those family trees. (In other words, for each of the corresponding trees determine the maximum distance, and return the maximum of those maximums.) |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Limits |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | num will contain between 2 and 20 elements, inclusive. | ||||||||||||
| - | Each element of num will be between 1 and n-1, inclusive. | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
题意:告诉每个点有几个儿子,如果是根节点,有num[i]个,否则有num[i-1]个.问这样的树是否存在,若存在,问树上两点的最大距离
分析:这里的num[i]就相当于每个结点的度数,有个性质:deg = 2 * n - 2可以判断树是否存在.然后最大距离一定是在两个叶子结点产生,因为树可以变化,总可以找到除了其他子节点外,其他所有点都在最大距离的路径里,答案就是 1 + cnt (num[i] > 1)的个数.我还傻傻的直接构造一棵树求LCA.....,但是好像还留在div1:)
class VampireTree {
public:
int maxDistance( vector <int> num ) {
int n = num.size ();
int deg = 0, ans = 1;
for (int i=0; i<n; ++i) {
deg += num[i];
if (num[i] > 1) ans++;
}
if (deg != 2 * n - 2) return -1;
else return ans;
}
};