第 6 章 树上问题

// 树的基本信息：一次 DFS 求出每个点的父亲、深度、子树大小、DFS 序。以 1 号点为根。
// 输入：n，接着 n-1 行 u v（树边）。
// 输出四行：fa[1..n]（根的父亲记 0）、dep[1..n]（根的深度记 1）、siz[1..n]、dfn[1..n]（儿子按编号从小到大访问）。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int fa[N], dep[N], siz[N], dfn[N], timer;

void dfs(int u, int parent) {
    fa[u] = parent;
    dep[u] = dep[parent] + 1;  // dep[0] 是 0，所以根的深度是 1
    siz[u] = 1;                // 先算上自己
    dfn[u] = ++timer;          // 进入 u 的时刻。u 的子树正好占据 DFS 序上 dfn[u] 到 dfn[u]+siz[u]-1 这一段
    for (int v : adj[u]) {
        if (v == parent) continue;  // 无向边会指回父亲，跳过，否则死循环
        dfs(v, u);
        siz[u] += siz[v];           // 儿子的子树算完了，累加上来
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // 树也是无向图，边存两次
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end());  // 只为让 DFS 序唯一，平时不需要这一行
    dfs(1, 0);
    for (int i = 1; i <= n; i++) cout << fa[i] << " \n"[i == n];
    for (int i = 1; i <= n; i++) cout << dep[i] << " \n"[i == n];
    for (int i = 1; i <= n; i++) cout << siz[i] << " \n"[i == n];
    for (int i = 1; i <= n; i++) cout << dfn[i] << " \n"[i == n];
    return 0;
}

dep[1] = 1;
for (int i = 2; i <= n; i++) dep[i] = dep[fa[i]] + 1;  // 正着扫：轮到 i 时，它的父亲已经算过
for (int i = 1; i <= n; i++) siz[i] = 1;
for (int i = n; i >= 2; i--) siz[fa[i]] += siz[i];     // 倒着扫：轮到 i 时，它的儿子都已经加进来了

// 不用递归求父亲、深度、子树大小：先 BFS 得到“从上到下”的顺序，再把这个顺序倒过来扫一遍。以 1 号点为根。
// 输入：n，接着 n-1 行 u v。输出三行：fa[1..n]（根记 0）、dep[1..n]（根记 1）、siz[1..n]。
#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
vector<int> adj[N];
int fa[N], dep[N], siz[N];
int order[N];  // BFS 的访问顺序。父亲一定排在儿子前面；倒过来看，儿子一定排在父亲前面

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int head = 1, tail = 0;  // 直接拿 order 数组当队列用
    order[++tail] = 1;
    dep[1] = 1;
    while (head <= tail) {  // 第一遍，从上到下：父亲的信息传给儿子（父亲、深度）
        int u = order[head++];
        for (int v : adj[u]) {
            if (v == fa[u]) continue;
            fa[v] = u;
            dep[v] = dep[u] + 1;
            order[++tail] = v;
        }
    }
    for (int i = n; i >= 1; i--) {  // 第二遍，从下到上：儿子的信息交给父亲（子树大小）
        int u = order[i];
        siz[u] += 1;                // 轮到 u 时，它的儿子都已经处理完，再加上自己就是最终值
        siz[fa[u]] += siz[u];       // 交给父亲。根的父亲是 0 号，加到 siz[0] 上没有影响
    }
    for (int i = 1; i <= n; i++) cout << fa[i] << " \n"[i == n];
    for (int i = 1; i <= n; i++) cout << dep[i] << " \n"[i == n];
    for (int i = 1; i <= n; i++) cout << siz[i] << " \n"[i == n];
    return 0;
}

for (int i = n; i >= 1; i--) {  // 倒着扫：轮到 u 时，它的儿子都已经把结果交上来了
    int u = order[i];
    f[u][1] += r[u];                       // 儿子们交上来的是 f[v][0] 之和，这里补上 u 自己
    f[fa[u]][1] += f[u][0];                // 再把 u 的结果交给父亲
    f[fa[u]][0] += max(f[u][0], f[u][1]);
}

// 树的直径：树上相距最远的两个点之间的距离。
// 两次 BFS：从任意一点出发找到最远的点 A，再从 A 出发找到最远的点 B，A 到 B 的距离就是直径。
// 输入：n，接着 n-1 行 u v w（边权非负）。输出：直径的长度。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 200005;
vector<pair<int, int>> adj[N];
ll dist[N];

int farthest(int s, int n) {  // 求 s 到所有点的距离，返回离 s 最远的点
    for (int i = 1; i <= n; i++) dist[i] = -1;
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto &e : adj[u]) {
            int v = e.first, w = e.second;
            if (dist[v] != -1) continue;  // 树上两点之间只有一条路，第一次到达时算出的就是距离
            dist[v] = dist[u] + w;
            q.push(v);
        }
    }
    return max_element(dist + 1, dist + n + 1) - dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    int a = farthest(1, n);  // 离 1 最远的点一定是某条直径的一个端点
    int b = farthest(a, n);
    cout << dist[b] << '\n';
    return 0;
}

ll down1[N], ans;  // down1[u]：从 u 往下走的最长距离（可以不走，所以至少是 0）
void dfs(int u, int parent) {
    for (auto &e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == parent) continue;
        dfs(v, u);
        ans = max(ans, down1[u] + down1[v] + w);  // 先用“之前最长的一条”和“新的这一条”拼出经过 u 的路径
        down1[u] = max(down1[u], down1[v] + w);   // 再把新的这一条并进来。这两行的顺序不能反
    }
}

// 树的重心：删掉这个点后，剩下的若干连通块里最大的那一块尽量小。重心有 1 个或 2 个。
// 输入：n，接着 n-1 行 u v。输出：一行，所有重心的编号，从小到大。
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
vector<int> adj[N];
int siz[N], worst[N], n;  // worst[u]：删掉 u 之后，最大的连通块有多少个点

void dfs(int u, int parent) {
    siz[u] = 1;
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
        siz[u] += siz[v];
        worst[u] = max(worst[u], siz[v]);  // 往下：每个儿子的子树是一块
    }
    worst[u] = max(worst[u], n - siz[u]);  // 往上：整棵树去掉 u 的子树，剩下的是一块
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    int best = *min_element(worst + 1, worst + n + 1);
    vector<int> centroids;
    for (int i = 1; i <= n; i++)
        if (worst[i] == best) centroids.push_back(i);
    for (size_t i = 0; i < centroids.size(); i++) cout << centroids[i] << " \n"[i + 1 == centroids.size()];
    return 0;
}

int lca_slow(int a, int b) {  // 每次询问最坏要走 O(n) 步
    while (a != b) {
        if (dep[a] < dep[b]) swap(a, b);  // 让 a 是更深的那个
        a = fa[a];                        // 深的那个往上走一步
    }
    return a;
}

// LCA（最近公共祖先）的倍增写法。洛谷 P3379 的格式。
// 输入：n m s（s 是根），接着 n-1 行树边，再接着 m 行询问 a b。输出：每个询问一行，a 和 b 的最近公共祖先。
#include <bits/stdc++.h>
using namespace std;

const int N = 500005, LOG = 20;  // 2^19 = 524288 > 5e5，向上跳的步数用 19 个二进制位就能表示，LOG 取 20 留一点余量
vector<int> adj[N];
int up[N][LOG], dep[N];          // up[u][k]：u 向上跳 2^k 步到达的点；跳出树了就是 0

void dfs(int u, int parent) {
    up[u][0] = parent;
    dep[u] = dep[parent] + 1;    // 根的深度是 1，0 号点（树外）的深度是 0
    for (int k = 1; k < LOG; k++) up[u][k] = up[up[u][k - 1]][k - 1];  // 跳 2^k 步 = 先跳 2^(k-1) 步，再跳 2^(k-1) 步
    for (int v : adj[u])
        if (v != parent) dfs(v, u);
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);    // 保证 a 是更深的那个
    for (int k = LOG - 1; k >= 0; k--)  // 第一步：把 a 提到和 b 一样深。k 必须从大到小
        if (dep[up[a][k]] >= dep[b]) a = up[a][k];
    if (a == b) return a;               // b 本来就是 a 的祖先
    for (int k = LOG - 1; k >= 0; k--)  // 第二步：两个点一起往上跳，只要跳完还不相遇就跳
        if (up[a][k] != up[b][k]) a = up[a][k], b = up[b][k];
    return up[a][0];                    // 现在两个点不同、但父亲相同，父亲就是答案
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(s, 0);
    while (m--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    return 0;
}

int kth_ancestor(int u, int d) {  // 从 u 往上走 d 步；走出树了返回 0
    for (int k = 0; k < LOG; k++)
        if (d >> k & 1) u = up[u][k];
    return u;
}

// 树上差分（点差分）：给出 m 条路径，每条路径上的所有点都加 1，问最后值最大的点是多少。洛谷 P3128 的格式。
// 输入：n m，接着 n-1 行树边，再接着 m 行 s t（一条路径的两个端点）。输出：最大的点值。
#include <bits/stdc++.h>
using namespace std;

const int N = 50005, LOG = 17;
vector<int> adj[N];
int up[N][LOG], dep[N];
int diff[N];  // 差分数组：先只在几个点上打标记，最后“子树内标记之和”才是每个点真正的值

void dfs(int u, int parent) {
    up[u][0] = parent;
    dep[u] = dep[parent] + 1;
    for (int k = 1; k < LOG; k++) up[u][k] = up[up[u][k - 1]][k - 1];
    for (int v : adj[u])
        if (v != parent) dfs(v, u);
}

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int k = LOG - 1; k >= 0; k--)
        if (dep[up[a][k]] >= dep[b]) a = up[a][k];
    if (a == b) return a;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[a][k] != up[b][k]) a = up[a][k], b = up[b][k];
    return up[a][0];
}

void collect(int u, int parent) {  // 把子树里的标记累加上来
    for (int v : adj[u]) {
        if (v == parent) continue;
        collect(v, u);
        diff[u] += diff[v];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    while (m--) {
        int s, t;
        cin >> s >> t;
        int p = lca(s, t);
        diff[s]++, diff[t]++;  // s 和 t 各往上“发”一个 +1，一直影响到根
        diff[p]--;             // 两个 +1 在 lca 汇合，lca 被多算了一次，减掉一个
        diff[up[p][0]]--;      // lca 的父亲及更上面的点不在路径上，把剩下的那个 +1 也抵消
    }
    collect(1, 0);
    cout << *max_element(diff + 1, diff + n + 1) << '\n';
    return 0;
}

diff[s]++, diff[t]++;
diff[lca(s, t)] -= 2;  // lca 管的是它上面的那条边，不在路径上

bool in_subtree(int u, int v) {  // v 在不在 u 的子树里（v == u 也算）
    return dfn[u] <= dfn[v] && dfn[v] <= dfn[u] + siz[u] - 1;
}

// 树形 DP（选 / 不选）：没有上司的舞会。洛谷 P1352 的格式。
// 输入：n，接着 n 行每人的快乐值 r_i（可以是负数），再接着 n-1 行 l k（k 是 l 的直接上司）。
// 输出：选一些人参加舞会，任何人都不和自己的直接上司同时参加，快乐值之和最大是多少。
#include <bits/stdc++.h>
using namespace std;

const int N = 6005;
vector<int> son[N];
int r[N];
int f[N][2];  // f[u][1]：u 参加时，u 的子树里快乐值之和的最大值；f[u][0]：u 不参加时的最大值
bool has_boss[N];

void dfs(int u) {
    f[u][1] = r[u];
    f[u][0] = 0;
    for (int v : son[u]) {
        dfs(v);                            // 先算完儿子，再用儿子的结果算自己
        f[u][1] += f[v][0];                // u 参加，儿子就不能参加
        f[u][0] += max(f[v][0], f[v][1]);  // u 不参加，儿子参加与否取较大的
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> r[i];
    for (int i = 1; i < n; i++) {
        int l, k;
        cin >> l >> k;
        son[k].push_back(l);  // 输入直接给了上下级，只存“上司 -> 下属”这一个方向
        has_boss[l] = true;
    }
    int root = 1;
    while (has_boss[root]) root++;  // 没有上司的那个人是根。题目没说根是 1，不能想当然
    dfs(root);
    cout << max(f[root][0], f[root][1]) << '\n';
    return 0;
}

// 树上背包：选课。洛谷 P2014 的格式。
// 输入：n m，接着 n 行 k_i s_i（第 i 门课的先修课是 k_i，0 表示没有先修课；学分是 s_i）。
// 输出：选 m 门课（要选一门课，必须先选它的先修课），学分之和最大是多少。
#include <bits/stdc++.h>
using namespace std;

const int N = 305;
vector<int> son[N];
int s[N], siz[N];
int f[N][N];  // f[u][j]：在 u 的子树里选 j 门课，并且一定选了 u，学分之和的最大值

void dfs(int u) {
    siz[u] = 1;
    f[u][1] = s[u];  // 只选 u 自己
    for (int v : son[u]) {
        dfs(v);
        for (int j = siz[u]; j >= 1; j--)      // j：在 u 和已经合并的儿子里选几门。倒序，保证读到的 f[u][j] 还没被 v 更新过
            for (int k = 1; k <= siz[v]; k++)  // k：在 v 的子树里选几门
                f[u][j + k] = max(f[u][j + k], f[u][j] + f[v][k]);
        siz[u] += siz[v];  // 合并完才把 v 的大小算进来：两层循环的范围都不超过实际的点数
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k >> s[i];
        son[k].push_back(i);  // 没有先修课的课挂在虚拟的 0 号课下面，一片森林就连成了一棵树
    }
    dfs(0);
    cout << f[0][m + 1] << '\n';  // 0 号课必选、学分是 0，所以总共要选 m+1 门
    return 0;
}

// 换根 DP：以哪个点为根时，所有点的深度之和最大（深度 = 到根要走几条边）。洛谷 P3478 的模型。
// 输入：n，接着 n-1 行 u v。输出：一个点的编号；有多个答案时输出编号最小的。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1000005;
vector<int> adj[N];
int fa[N], order[N];  // order：BFS 序，父亲排在儿子前面（写法见 tree_bfs_order.cpp）
ll siz[N];
ll down[N];           // down[u]：以 1 为根时，u 的子树里所有点到 u 的距离之和
ll f[N];              // f[u]：以 u 为根时，所有点的深度之和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int head = 1, tail = 0;
    order[++tail] = 1;
    while (head <= tail) {
        int u = order[head++];
        for (int v : adj[u])
            if (v != fa[u]) fa[v] = u, order[++tail] = v;
    }
    for (int i = n; i >= 1; i--) {  // 第一遍，自下而上：只看子树里面，算出 siz 和 down
        int u = order[i];
        siz[u] += 1;
        siz[fa[u]] += siz[u];
        down[fa[u]] += down[u] + siz[u];  // u 的子树里每个点到 fa[u]，都比到 u 多走一条边
    }
    f[1] = down[1];                 // 根的答案就是 down
    for (int i = 2; i <= n; i++) {  // 第二遍，自上而下：用父亲的答案推出儿子的答案
        int u = order[i];
        f[u] = f[fa[u]] - siz[u] + (n - siz[u]);  // 根从 fa[u] 挪到 u：u 子树里的点各近 1，其余的点各远 1
    }
    int best = 1;
    for (int i = 2; i <= n; i++)
        if (f[i] > f[best]) best = i;
    cout << best << '\n';
    return 0;
}

ll solve_brute() {  // n <= 20：每个点选或不选，一共 2^n 种，逐个检查
    ll best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        bool ok = true;
        for (int i = 1; i < n && ok; i++)  // 有没有哪条边的两端同时被选。eu[i]、ev[i] 是第 i 条边的两个端点
            if ((mask >> (eu[i] - 1) & 1) && (mask >> (ev[i] - 1) & 1)) ok = false;
        if (!ok) continue;
        ll sum = 0;
        for (int i = 1; i <= n; i++)
            if (mask >> (i - 1) & 1) sum += a[i];
        best = max(best, sum);
    }
    return best;
}

// 认出两种特殊形态的树：链（每个点最多连两条边）和菊花（有一个点连着其余所有的点）。
// 数据范围表里的“特殊性质”常常就是这两种，认出来就能换成简单得多的做法。
// 输入：n，接着 n-1 行 u v。
// 输出两行。第一行：是链就输出 CHAIN，后面跟着从编号较小的端点出发沿链依次经过的点；不是链输出 NOT_CHAIN。
//          第二行：是菊花就输出 STAR 和中心的编号（有多个点符合时取编号最小的）；不是菊花输出 NOT_STAR。
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
vector<int> adj[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bool chain = true;
    int start = 0, center = 0;
    for (int i = 1; i <= n; i++) {
        int degree = adj[i].size();                   // 度数：这个点连着几条边
        if (degree > 2) chain = false;                // 链上每个点最多两个邻居
        if (degree <= 1 && start == 0) start = i;     // 邻居不超过一个的点是链的端点，取编号最小的那个
        if (degree == n - 1 && center == 0) center = i;  // 连着其余所有点的，就是菊花的中心
    }
    if (!chain) {
        cout << "NOT_CHAIN\n";
    } else {
        cout << "CHAIN";
        for (int prev = 0, cur = start; cur != 0;) {  // 从端点出发，每一步走向“不是刚才来的那个”邻居
            cout << ' ' << cur;
            int next = 0;
            for (int v : adj[cur])
                if (v != prev) next = v;
            prev = cur, cur = next;
        }
        cout << '\n';
    }
    if (center == 0) cout << "NOT_STAR\n";
    else cout << "STAR " << center << '\n';
    return 0;
}

ll solve_chain() {  // 链：序列上相邻的两个不能同时选
    ll take = a[seq[1]], skip = 0;  // take：选了当前点时的最大和；skip：没选当前点时的最大和
    for (int i = 2; i <= n; i++) {
        ll new_take = skip + a[seq[i]];
        ll new_skip = max(take, skip);
        take = new_take, skip = new_skip;
    }
    return max(take, skip);
}

int l = min(pos[s], pos[t]), r = max(pos[s], pos[t]);  // 路径 s..t 就是链上的第 l 个到第 r 个点
d[l]++, d[r + 1]--;                                    // 全部加完后求前缀和，点 v 的值是 d[pos[v]]

ll solve_star(int center) {  // 菊花：选了中心就不能选叶子；不选中心，叶子互不相邻，正的全选
    ll leaves = 0;
    for (int i = 1; i <= n; i++)
        if (i != center && a[i] > 0) leaves += a[i];
    return max((ll)a[center], leaves);
}