树的孩子兄弟表示法：给每棵树配上 左儿子右兄弟 的骨架

const int MAXN = 100005;
int lc[MAXN], rs[MAXN];   // lc: 第一个孩子；rs: 下一个兄弟
int fa[MAXN];             // 可选：同时记录父亲，方便向上走

// ① 给 u 添加一个孩子 v（头插法，O(1)）
void addChild(int u, int v) {
    rs[v] = lc[u];        // v 的弟弟是原来的长子
    lc[u] = v;            // u 的长子变为 v
    fa[v] = u;
}

// ② 枚举 u 的所有孩子：沿 rs 链走
void listChildren(int u) {
    for (int v = lc[u]; v != 0; v = rs[v])
        printf("%d ", v);
}

// ③ 求 u 的父亲：沿 rs 链走到末端，末端的 fa 就是 u 的父
int getFather(int u) {
    while (rs[u] != 0) u = rs[u];   // 走到兄弟链尾部
    return fa[u];
}

// ④ 计算子树的节点数（原树意义下的子树）
int subtreeSize(int u) {
    if (u == 0) return 0;
    int cnt = 1;                         // 自己
    for (int v = lc[u]; v != 0; v = rs[v])
        cnt += subtreeSize(v);              // 每个孩子的整棵子树
    return cnt;
}

// 输入：n 个节点，每行给出 u 的儿子列表（以 0 结束）
// 输出：lc[] / rs[] 两个数组
const int MAXN = 100005;
int lc[MAXN], rs[MAXN], fa[MAXN];

void build() {
    int n; scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        int v, prev = 0, first = 0;
        while (scanf("%d", &v) && v != 0) {
            fa[v] = u;
            if (prev == 0) first = v;   // 记下长子
            else rs[prev] = v;             // 弟弟链：前一个的右指针指向当前
            prev = v;
        }
        lc[u] = first;                     // 父亲只认长子
    }
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;
int lc[MAXN], rs[MAXN], w[MAXN], v[MAXN];
int n, m;
int f[MAXN][MAXN];          // f[u][j]: 以 u 为根的兄弟森林容量 j 的最优值

int dfs(int u, int j) {
    if (u == 0 || j <= 0) return 0;
    if (f[u][j] != -1) return f[u][j];
    // 选项一：不选 u，直接跳到下一个兄弟
    int best = dfs(rs[u], j);
    // 选项二：选 u，需要先扣掉 w[u]
    if (j >= w[u]) {
        int rem = j - w[u];
        for (int k = 0; k <= rem; k++) {   // 剩余容量切给长子/兄弟
            best = max(best, v[u] + dfs(lc[u], rem - k) + dfs(rs[u], k));
        }
    }
    return f[u][j] = best;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
    // 建树：父亲 i/2 的孩子是 i（此处以完全二叉树父亲为例）
    for (int i = n; i >= 1; i--) {
        int p = i / 2;
        if (p >= 1) { rs[i] = lc[p]; lc[p] = i; }
    }
    memset(f, -1, sizeof(f));
    printf("%d\n", dfs(1, m));        // 必须从根 1 开始（含"选根"决策）
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int lc[MAXN], rs[MAXN], fa[MAXN];
vector<int> ans;

void preOrder(int u) {
    if (u == 0) return;
    ans.push_back(u);                        // 访问自己
    for (int v = lc[u]; v != 0; v = rs[v])
        preOrder(v);                          // 依次访问每个孩子
}

int main() {
    int n;
    scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        int v, prev = 0;
        while (scanf("%d", &v) && v != 0) {
            fa[v] = u;
            if (prev == 0) lc[u] = v;   // 第一个儿子当长子
            else rs[prev] = v;             // 后续儿子接到弟弟链
            prev = v;
        }
    }
    int root = 1;
    for (int i = 1; i <= n; i++) if (fa[i] == 0) { root = i; break; }
    preOrder(root);
    for (size_t i = 0; i < ans.size(); i++)
        printf("%d%c", ans[i], i + 1 == ans.size() ? '\n' : ' ');
    return 0;
}

void preB(int u) {          // 二叉树先序
    if (!u) return;
    printf("%d ", u);
    preB(lc[u]); preB(rs[u]);
}

void inB(int u) {           // 二叉树中序
    if (!u) return;
    inB(lc[u]);
    printf("%d ", u);
    inB(rs[u]);
}

void postT(int u) {         // 原树后序
    if (!u) return;
    for (int v = lc[u]; v; v = rs[v]) postT(v);
    printf("%d ", u);
}

// 输出对比：
// 二叉树先序: 1 2 5 8 6 3 7 4   = 原树先序 ✓
// 二叉树中序: 8 5 6 2 7 3 4 1   = 原树后序 ✓
// 原树后序  : 8 5 6 2 7 3 4 1   = 二叉树中序 ✓

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int lc[MAXN], rs[MAXN], sz[MAXN];

int dfs(int u) {
    if (u == 0) return 0;
    int tot = 1;                                 // 自己
    for (int v = lc[u]; v != 0; v = rs[v])
        tot += dfs(v);                              // 加上每个孩子的整棵子树
    return sz[u] = tot;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        int v, prev = 0;
        while (scanf("%d", &v) && v != 0) {
            if (prev == 0) lc[u] = v; else rs[prev] = v;
            prev = v;
        }
    }
    dfs(1);
    for (int i = 1; i <= n; i++) printf("sz[%d]=%d\n", i, sz[i]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int lc[MAXN], rs[MAXN];

void preOrder(int u) {
    if (!u) return;
    printf("%d ", u);
    for (int v = lc[u]; v; v = rs[v]) preOrder(v);
}

void postOrder(int u) {
    if (!u) return;
    for (int v = lc[u]; v; v = rs[v]) postOrder(v);  // 先处理所有孩子
    printf("%d ", u);                                    // 最后才输出自己
}

int main() {
    int n;
    scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        int v, prev = 0;
        while (scanf("%d", &v) && v != 0) {
            if (prev == 0) lc[u] = v; else rs[prev] = v;
            prev = v;
        }
    }
    preOrder(1);  printf("\n");
    postOrder(1); printf("\n");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int lc[MAXN], rs[MAXN], sz[MAXN];

void dfs(int u) {
    sz[u] = 1;
    for (int v = lc[u]; v; v = rs[v]) {
        dfs(v);                  // 先把孩子算完
        sz[u] += sz[v];
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        int v, prev = 0;
        while (scanf("%d", &v) && v != 0) {
            if (prev == 0) lc[u] = v; else rs[prev] = v;
            prev = v;
        }
    }
    dfs(1);
    int best = -1, bestId = 1;
    for (int i = 1; i <= n; i++) {
        printf("%d\n", sz[i]);
        if (sz[i] > best) { best = sz[i]; bestId = i; }  // 严格大于才更新 → 取最小编号
    }
    printf("%d\n", bestId);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int lc[MAXN], rs[MAXN];

void inOrder(int u) {           // 标准二叉树中序
    if (!u) return;
    inOrder(lc[u]);
    printf("%d ", u);
    inOrder(rs[u]);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        int v, prev = 0;
        while (scanf("%d", &v) && v != 0) {
            if (prev == 0) lc[u] = v; else rs[prev] = v;
            prev = v;
        }
    }
    for (int i = 1; i <= n; i++) printf("%d %d\n", lc[i], rs[i]);
    inOrder(1);
    printf("\n");
    return 0;
}

const int MAXN = 100005;
int lc[MAXN], rs[MAXN], fa[MAXN];
int n;

// ===== 建树：从「每个节点的儿子列表」构造孩子兄弟 =====
void build() {
    scanf("%d", &n);
    for (int u = 1; u <= n; u++) {
        int v, prev = 0;
        while (scanf("%d", &v) && v != 0) {
            fa[v] = u;
            if (!prev) lc[u] = v;    // 首个儿子 → 长子
            else rs[prev] = v;        // 其余 → 弟弟链
            prev = v;
        }
    }
}

// ===== 原树先序 =====
void preOrder(int u) {
    if (!u) return;
    printf("%d ", u);
    for (int v = lc[u]; v; v = rs[v]) preOrder(v);
}

// ===== 原树后序 =====
void postOrder(int u) {
    if (!u) return;
    for (int v = lc[u]; v; v = rs[v]) postOrder(v);
    printf("%d ", u);
}

// ===== 子树大小 =====
int sz[MAXN];
int getSize(int u) {
    if (!u) return 0;
    int t = 1;
    for (int v = lc[u]; v; v = rs[v]) t += getSize(v);
    return sz[u] = t;
}

// ===== 二叉树视角的两种遍历（用于验证对应关系）=====
void preB(int u) { if(!u) return; printf("%d ",u); preB(lc[u]); preB(rs[u]); }
void inB(int u)  { if(!u) return; inB(lc[u]); printf("%d ",u); inB(rs[u]); }

// 各棵树的根：root[1..k]，把它们串成一条 rs 链
void forestToBinary(int roots[], int k) {
    for (int i = 1; i < k; i++)
        rs[roots[i]] = roots[i + 1];   // 第 i 棵树的根 → 指向第 i+1 棵
    rs[roots[k]] = 0;
}
// 遍历时从 roots[1] 出发，二叉树的"右子树"就是后续的树

int h[MAXN], diameter = 0;

void dfs(int u) {
    int mx1 = 0, mx2 = 0;          // 孩子中最大/次大的子树高度
    for (int v = lc[u]; v; v = rs[v]) {
        dfs(v);
        if (h[v] > mx1) { mx2 = mx1; mx1 = h[v]; }
        else if (h[v] > mx2) mx2 = h[v];
    }
    h[u] = mx1 + 1;                    // 自身为叶时 h=1
    diameter = max(diameter, mx1 + mx2);  // 经过 u 的最长路径
}

// 一棵树的高度 = h[root]，直径 = diameter（边数）

int f[MAXN][MAXM];              // -1 表示未计算

int dp(int u, int j) {
    if (!u || j <= 0) return 0;
    if (f[u][j] != -1) return f[u][j];
    int best = dp(rs[u], j);                  // 不选 u
    if (j >= w[u]) {
        int rem = j - w[u];
        for (int k = 0; k <= rem; k++)
            best = max(best, v[u] + dp(lc[u], rem - k) + dp(rs[u], k));
    }
    return f[u][j] = best;
}