遍历树,获取每个节点的深度。对每个节点,考虑深度差最大的两个子树(即获取到一个较大时延),以及子树中最大的时延,比较得出最大。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
#include<vector> #include<algorithm> using namespace std; const int N = 20015; vector<int> tree[N]; #define getMax2Deep(a,b,c) (c>a?(b=a,a=c):((c>b)?(b=c):(1))) int deep[N] = { 0 }; int n, m; void () { int i = 2; int root; fill(deep, deep + N, 0); while (i<=n) { cin >> root; tree[root].push_back(i); i++; } while (i<=n + m) { cin >> root; tree[root].push_back(i); i++; } } int dfs(int root = 1) { int maxDelay = 0; int maxDeep = 0, max2deep = 0; if (tree[root].size() == 0) { deep[root] = 1; return 1; } for (int i = 0; i<tree[root].size(); i++) { maxDelay = max(maxDelay, dfs(tree[root][i])); getMax2Deep(maxDeep, max2deep, deep[tree[root][i]]); } deep[root] = maxDeep + 1; return max(maxDelay, maxDeep+max2deep); } int main() { freopen("in.txt", "r", stdin); cin >> n >> m; buildTree(); cout << dfs(); return 0; }
|
近期评论