8.14信息学集训_树、搜索与剪枝

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 310, INF = 0x3f3f3f3f;
char a, b, c, rt, tr[N][2];
int n;
// pre(u) : 先序遍历以 u 为根的子树
void pre(char u) {
    if (u == '*')
        return;
    cout << u;      // 遍历 u,即根节点
    pre(tr[u][0]);  // 遍历 u 的左儿子
    pre(tr[u][1]);  // 遍历 u 的右儿子
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> b >> c;
        if (i == 0)
            rt = a;
        tr[a][0] = b;
        tr[a][1] = c;
    }
    pre(rt);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6, INF = 0x3f3f3f3f;
int n, tr[N][2];
// struct Node {
//     int l, r;
// } tree[N]; // 还可以使用结构体封装左右儿子

// pre(u) : 先序遍历以 u 为根的子树
void pre(int u) {
    if (u == 0)
        return;
    cout << u << " ";  // 遍历 u,即根节点
    pre(tr[u][0]);     // 遍历 u 的左儿子
    pre(tr[u][1]);     // 遍历 u 的右儿子
}
void in(int u) {
    if (u == 0)
        return;
    in(tr[u][0]);      // 遍历 u 的左儿子
    cout << u << " ";  // 遍历 u,即根节点
    in(tr[u][1]);      // 遍历 u 的右儿子
}
void post(int u) {
    if (u == 0)
        return;
    post(tr[u][0]);    // 遍历 u 的左儿子
    post(tr[u][1]);    // 遍历 u 的右儿子
    cout << u << " ";  // 遍历 u,即根节点
}

int main() {
    cin >> n;
    for (int i = 1, l, r; i <= n; i++) {
        cin >> l >> r;
        tr[i][0] = l, tr[i][1] = r;
    }
    pre(1), cout << endl;
    in(1), cout << endl;
    post(1), cout << endl;
    return 0;
}

#include <bits/stdc++.h>  // 万能头
using namespace std;
const int N = 1e6 + 10;
struct T {
    int l, r;
} tree[N];

int dfs(int rt) {
    if (tree[rt].l == 0 && tree[rt].r == 0) return 1;
    return max(dfs(tree[rt].l), dfs(tree[rt].r)) + 1;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1, l, r; i <= n; i++) {
        scanf("%d%d", &l, &r);
        tree[i].l = l;
        tree[i].r = r;
    }
    printf("%d\n", dfs(1));
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6, INF = 0x3f3f3f3f;
vector<int> g[N];
int n, v1, v2, v3, dep[N], st[N], p[N];

void dfs(int u, int d) {
    dep[u] = d, v1 = max(v1, d), v2 = max(v2, ++st[d]);
    for (auto v : g[u]) {
        p[v] = u, dfs(v, d + 1);
    }
}
int main() {
    cin >> n;
    int u, v;
    for (int i = 1; i <= n; i++) {
        cin >> u >> v;
        if (i < n) g[u].push_back(v);
    }
    dfs(1, 1);
    // u -> v
    int up = 0, down = 0;
    while (dep[u] > dep[v]) u = p[u], up++;
    while (dep[u] < dep[v]) v = p[v], down++;
    while (u != v) u = p[u], v = p[v], up++, down++;
    v3 = 2 * up + down;
    cout << v1 << endl << v2 << endl << v3 << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int tr[N], w[N], k, n;
// w[d] :表示深度 d 的所有节点权值和
// dfs(u,d) : 遍历 u为 根节点的子树，深度为 d
void dfs(int u, int d) {
    if (u > n) return;
    w[d] += tr[u], k = max(k, d);
    dfs(2 * u, d + 1);
    dfs(2 * u + 1, d + 1);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &tr[i]);  // 建树
    dfs(1, 1);

    int id = 1; // 节点权值和最大的深度
    for (int i = 1; i <= k; i++)
        if (w[id] < w[i]) id = i;
    printf("%d", id);
    return 0;
}