UVA 11688 Rotate to root

dp uva

這是別人的解釋

可是看了別人的解釋之後, 我還是花了很多時間才明白, 所以記一下理解的方法.

若果單是第二層的點轉到最頂層是很容易明白的, 可是把第三層的點如何才能轉到最頂層呢?

比較容易理解(想出上面公式的正確性)的方法如下.
就是不停把 X 轉到自己父節點的位置, 直到自己是根節點.

當我們把 X 轉到父節點時, 他的樹結構和原本的樹是差不多的, 不同就是他多(左移/右移)了一步及他的其中一個子樹會移到父節點下面.

而左移/右移的次數對應 dl, dr.

而計算高度時, 我們會用到hl, hr, dl, dr這些狀態, 雖然我們不能直即得出轉到根節點時的狀態值, 但我們知道把 X 轉到父節點時的狀態轉變.
把父節點轉到根節點時的狀態值加上由 X 轉到父節點時的狀態轉變, 就是 X 轉到根節點時的狀態值.

因此我們可以把它反過來, 由根節點不停計算下去, 把子節點轉到父節點的狀態轉變加下去.\

uva11688.cpp
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 100010;

typedef struct node {
  int left, right;
  node() {}
} Node;

Node nodes[MAXN];

int maxH[MAXN];
int parent[MAXN];
int dp[MAXN];

int getHeight(int nodeno) {
  if(maxH[nodeno] != -1)
    return maxH[nodeno];
  if(nodeno == 0)
    return 0;
  Node &no = nodes[nodeno];
  int lefth = getHeight(no.left);
  int righth = getHeight(no.right);
  maxH[nodeno] = 1 + max(lefth, righth);
  return maxH[nodeno];
}

void dfs(int curno, int lh, int rh, int lc, int rc) {
  if(curno == 0)
    return;

  int lsh = getHeight(nodes[curno].left);
  int rsh = getHeight(nodes[curno].right);

  dp[curno] = max( max(lh, rh), max(lsh + lc, rsh + rc)) + 1;
  dfs(nodes[curno].left, lh, max(rh, rsh + rc + 1), lc, rc+1);
  dfs(nodes[curno].right, max(lh, lsh + lc + 1), rh, lc+1, rc);
}


int main() {
  // freopen("input.txt", "r", stdin);

  int n;
  int root, leftest, rightest;
  int rootH = 0;

  while(scanf("%d", &n) != EOF && n) {
    memset(parent, 0, sizeof(parent));

    for(int i = 1; i <= n; ++i) {
      scanf("%d%d", &nodes[i].left, &nodes[i].right);
      parent[nodes[i].left] = i;
      parent[nodes[i].right] = i;
    }

    memset(maxH, -1, sizeof(maxH));
    for(int i = 1; i <= n; ++i)
      if(parent[i] == 0) {
        root = i;
        dfs(root, 0, 0, 0, 0);
        break;
      }

    for(int i = 1; i <= n; ++i)
      printf("%d\n", dp[i]);
  }

  return 0;
}