树

树

类别

树可以简单分为有根树和无根树

有根树

除了根节点以外，每个节点都存在父节点

数据结构

vector<int> edges[N + 1];
int father[N + 1];
void addedge(int x, int y) {
    edges[x].push_back(y);
}

DFS遍历

vector<int> dfn;
void dfs(int x) {
    dfn.push_back(x);
    for (auto y : edges[x]) {
        dfs(y);
    }
}
dfs(root);

BFS遍历

int q[100], front = 1, rear = 0
void bfs(int root) {
    q[++rear] = root;
    while (front <= rear) {
        int x = q[front];
        ++front;
        for (auto y : edges[x]) {
            q[++rear] = y;
        }
    }
}
bfs(root);

无根树

不存在子节点和父节点，只存在相邻节点

DFS遍历

在进入一个新的节点时，需要记录其来源的节点，遍历在遍历相邻节点时，重复处理

void dfs(int from , int x) {
    for (auto y : edges[x]) {
        if (y != from) {
            dfs(x, y);
        }
    }
}

BFS遍历

int q[100], front = 1, rear = 0;
void bfs(int x) {
    q[++rear] = x;
    int from = -1;
    while (front <= rear) {
        int x = q[front], ++front;
        // from = x的来源节点
        for (auto y : edges[x]) {
            if (y != from) {
                q[++rear] = y;
                // 记录y的来源节点为x
            }
        }
    }
}

树的直径

树的直径是指树上任意两个节点之间最长的路径

树的直径的中间节点被称为树的中心。如果直径上有偶数个节点，则中间的两个节点都可以称为树的中心。

树的中心到其它点的最长路径最短

求解树的直径

树的直径可以用两次搜索求得，第一次从任意一个节点开始搜索，找出距离最远的节点a。第二次从a节点开始搜索，找到距离节点a最远的节点b，则路径a-b即为树的直径。

// 计算无根树中直径的长度
int n, pre[1001], dist[1001];
vector<int> edges[1001];
void dfs(int x) {
    for (auto y : edges[x]) {
        if (y != pre[x]) {
            pre[y] = x;
            dist[y] = dist[x] + 1;
            dfs(y);
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    memset(dist, 0, sizeof(dist));
    memset(pre, 0, sizeof(pre));
    pre[1] = -1;
    dfs(1); // 从任意节点开始遍历
    int idx = 0, v = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > v)
            v = dist[i], idx = i;
    }
    memset(dist, 0, sizeof(dist));
    memset(pre, 0, sizeof(pre));
    pre[idx] = -1;
    dfs(idx); // 从找到的最远节点再次进行遍历
    v = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > v)
            v = dist[i];
    }
    printf("%d", v); // 此时计算得到的就是直径的长度
}

树的重心

对于无根树来说，以任意节点为根节点，其子树大小中的最大值，最小的那个节点，就是树的重心

一棵树可能有1或2个重心

性质

当重心为根节点时，它底下每个子树的大小不大于整棵树大小的一半

重心到其它所有节点的距离和最小

计算树的重心

以某个节点为根节点，对整棵树进行一次遍历，在遍历的同时记录下每个节点子树的大小

在计算以其它节点为根节点x时，因为已经计算过一部分子树的大小，只是没有计算它的来源节点作为子节点时，子树的大小，此时可以直接通过n - size[x]，即可得到来源节点子树的大小

最终每个节点作为根节点，子树的最大值，再从中找出最小的一个

int n, pre[101], size[101];;
vector<int> edges[101];

void solve(int x) {
    size[x] = 1;
    for (auto y : edges[x]) {
        if (y != pre[x]) {
            pre[y] = x;
            solve(y);
            size[x] += size[y];
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    memset(pre, 0, sizeof(pre));
    solve(1);
    int idx, v = 1 << 30;
    for (int i = 1; i <= n; i++) {
        int f = 0;
        for (auto y : edges[i]) {
            if (y != pre[x]) {
                f = max(f, size[y]);
            } else {
                f = max(f, n - size[x]);
            }
        }
        if (f < v) {
            v = f, idx = i;
        }
    }
    printf("%d", idx);
}

树的最近公共祖先

先对整棵树进行遍历，获取到每一个节点到根节点的距离

使用倍增的思想，将距离远的那个节点跳到与另一个节点同一层级

再次使用倍增，两个节点同时向上跳，找到最近的公共祖先

int n, dist[101], father[101][20];
vector<int> edges[101];

void dfs(int x) {
    for (auto y : edges[x]) {
        dist[y] = dist[x] + 1;
        dfs(y);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edges[x].push_back(y);
        father[y][0] = x;
    }
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j < n; j++) {
            if (father[j][i - 1]) {
                father[j][i] = father[father[j][i - 1]][i - 1];
            }
        }
    }
    memset(dist, 0, sizeof(dist));
    dfs(1);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int x, y; // 两个树上的节点
        scanf("%d%d", &x, &y);
        if (dist[x] < dist[y])
            swap(x, y);
        int z = dist[x] - dist[y];
        for (int j = 0; j <= 20 && z; j++, z /= 2) {
            if (z & 1)
                x = father[x][j];
        }
        if (x == y) {
            printf("%d\n", x);
            continue;
        }
        for (int j= 20; j >= 0; j--) {
            if (father[x][j] != father[y][j]) {
                x = father[x][j], y = father[y][j];
            }
        }
        printf("%d\n", father[x][0]);
    }
}