首页 > ACM题库 > HDU-杭电 > hdu 2499 Rotate to root-树形DP[解题报告]C++
2014
02-09

hdu 2499 Rotate to root-树形DP[解题报告]C++

Rotate to root

问题描述 :

Rotate-to-root is a heuristic for balancing binary search trees. In this problem, the contents of the tree will be ignored, and you will be asked about the effect the heuristic has on the structure of the tree.A binary tree is either empty or consists of a node with a left child and a right child, where each of the children are also binary trees. No node has more than one parent, and there are no cycles. In any non-empty tree, there is exactly one node without a parent, which is called the root of the tree.

The rotate-to-root heuristic takes effect when a node in the tree, say X, is accessed. While X is not the root of the tree, the following procedure is executed:

    • If X is the left child of its parent, a right tree rotation is performed. Let P be the parent of X, let A be X’s left child, let B be X’s right child, and let C be the right child of P. Then, P is replaced in the tree by X, so P’s parent (if any) becomes X’s parent; X’s right child becomes P’s left child (which replaces X); and P replaces X’s right child. Diagram:

 

  • If X is the right child of its parent, a left tree rotation is performed. Let P be the parent of X, let A be the left child of P, let be B be X’s left child, and let C be X’s right child. Then, P is replaced in the tree by X, so P’s parent (if any) becomes X’s parent; X’s left child becomes P’s right child (which replaces X); and P replaces X’s left child. Diagram:

 

Tree rotations preserve the order of the nodes in the tree, which is why they are useful, but that is not important for this problem.

The height of a binary tree is the longest length of a path from its root to the bottom of the tree. More formally, the height of the empty tree is 0, and the height of a non-empty tree that has a root node X with children A and B is 1 + max{height(A), height(B)}.

Given a binary tree, you must determine, for each node X, what the height of the tree would be after X is rotated to root.

输入:

Input consists of a number of test cases. The first line of each test case contains the integer N, the number of nodes in the binary tree, where 1 <= N <= 105.The following N lines of input each contain two integers. The ith pair of these integers is li and ri, the left and right children of node i. If li = 0, then the left child of node i is the empty tree, and if ri = 0, then the right child of node i is the empty tree. Otherwise, 1 <= l, r <= N.

It is guaranteed that the input will describe a binary tree.

The last test case is followed by a line containing the integer 0. This final line is not a test case and should not be processed.

输出:

Input consists of a number of test cases. The first line of each test case contains the integer N, the number of nodes in the binary tree, where 1 <= N <= 105.The following N lines of input each contain two integers. The ith pair of these integers is li and ri, the left and right children of node i. If li = 0, then the left child of node i is the empty tree, and if ri = 0, then the right child of node i is the empty tree. Otherwise, 1 <= l, r <= N.

It is guaranteed that the input will describe a binary tree.

The last test case is followed by a line containing the integer 0. This final line is not a test case and should not be processed.

样例输入:

4
2 3
4 0
0 0
0 0
0

样例输出:

3
3
4
3

Problem : 2499 ( Rotate to root )     Judge Status : Accepted
RunId : 10092982    Language : C++    Author : acmerblog
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
#include <cstdio>
#include <cstring>

const int N = 100010;

int n, root, f[N], l[N], r[N], d[N], w[N];

int max(int x, int y)
{
    return  x > y ? x : y;
}

void init(int u)
{
    if(u == 0)  return;
    init(l[u]);
    init(r[u]);
    d[u] = max(d[l[u]], d[r[u]])+1;
}

void dp(int x, int &lt, int &rt)
{
    int p;
    p = f[x];
    if(x == root)  return;
    if(l[p] == x)
    {
        w[p] = max(lt+1, max(rt, d[r[p]])+2);
        rt = max(rt, d[r[p]])+1;
    }
    else
    {
        w[p] = max(rt+1, max(d[l[p]], lt)+2);
        lt = max(d[l[p]], lt)+1;
    }
    dp(p, lt, rt);
}

int main()
{
    int i, a, b;
    while(scanf("%d", &n) != EOF)
    {
        if(n == 0)  break;
        for(i = 1; i <= n; i++)  f[i] = i;
        for(i = 1; i <= n; i++)
        {
            scanf("%d%d", &a, &b);
            f[a] = f[b] = i;
            l[i] = a;
            r[i] = b;
        }
        root = 1;
        while(f[root] != root)  root = f[root];
        d[0] = 0;
        init(root);
        for(i = 1; i <= n; i++)
        {
            w[0] = 0;
            a = d[l[i]];
            b = d[r[i]];
            if(i == root)  w[root] = max(d[l[root]], d[r[root]])+1;
            else  dp(i, a, b);
            printf("%d\n", w[root]);
        }
    }
    return  0;
}

 


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的