树形数据结构（一）

树与图的 dfs

树的 dfs

void dfs(int x) {
    vis[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y);
    }
}
int main() {
    dfs(1);
}

树的 dfs 序

dfs-01

vector<int> a;
void dfs(int x) {
    a.push_back(x);
    vis[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y);
    }
    a.push_back(x);
}

树的深度

$\textbf{for} \ \forall e(x, y)$
$\quad \quad d(y) = d(x) + 1$

memset(d, 0, sizeof d);
void dfs(int x) {
    vis[x] = 1;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        d[y] = d[x] + 1;
        dfs(y);
    }
}

树的重心

树的重心非常重要，是点分治中的重要算法
dfs-02

int res = inf, pos;
void gravity(int x, int &res) {
    vis[x] = 1; size[x] = 1;
    int maxpart = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dfs(y, res);
        size[x] += size[y];
        maxpart = max(maxpart, size[y]);
    }
    maxpart = max(maxpart, n - size[x]);
    if (maxpart < res) {
        res = maxpart;
        pos = x;
    }
}

图的连通块

int cnt = 0;
void dfs(int x) {
    v[x] = cnt;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (v[y]) continue;
        dfs(y);
    }
}

int main() {
    for (int i = 1; i <= n; i++) {
        if (!v[i]) {
            cnt++;
            dfs(i);
        }
    }
}

树和图的 bfs

bfs的性质

bfs 是逐层扩展的，并且每一次出队列的时候，才把队头元素的子节点，放入队列中
所以任何时刻，队列中的元素至多有 $2$ 个层次的节点
其中一部分节点属于第 $i$ 层，另一部分属于第 $i+1$ 层
在访问完第 $i$ 层节点后，才会访问第 $i+1$ 层
bfs 可以求出 $d$ 数组， $d(x)$ 表示从起点 $1$ 走到 $x$ 点
最少需要经过多少点

void bfs() {
    memset(d, 0, sizeof d);
    queue<int> q;
    q.push(1); d[1] = 1;
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            q.push(y);
        }
    }
}

拓扑排序

拓扑排序适用于有向无环图 (dag)
预处理入度数组 $\textbf{deg}[\cdots]$ ，把所有 $\textbf{deg}=0$ 的点入队
$x \leftarrow \text{front}()$ ，检查每一条边 $\textbf{for} \ \forall (x, y_k)$
$\textbf{if} \ --\textbf{deg}[y_k] = 0$ ， $\textbf{push}(y_k)$

Acwing164
用状态压缩来表示集合，不妨设 $f(x)$ 表示从 $x$ 出发能够到达的点构成的集合

$f(x) = \{x\} \cup \left( \bigcup_{(x, y) \text{存在有向边}} f(y)\right)$

const int maxn = 30000 + 10;
int head[maxn], ne[maxn], ver[maxn], deg[maxn], n, m, tot = 0;
vector<int> a;

void add(int x, int y) {
    ver[++tot] = y; ne[tot] = head[x]; head[x] = tot;
    deg[y]++;
}

void toposort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) q.push(i);
    }

    while (q.size()) {
        int x = q.front(); q.pop();
        a.push_back(x);
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (--deg[y] == 0) q.push(y);
        }
    }
}

bitset<maxn> f[maxn];
void solve() {
    for (int j = a.size()-1; j >= 0; j--) {
        int x = a[j];
        f[x][x] = 1;
        for (int i = head[x]; i; i = ne[i]) {
            f[x] |= f[ver[i]];
        }
    }

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

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m;

    // get edge
    memset(head, 0, sizeof head);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }

    toposort();
    solve();
}

树的直径

两次 bfs 求树的直径

从 $1$ 出发执行 $\textbf{bfs}(1)$ ，求出与出发点最远，即 $\text{d}[\ \ ]$ 最大的节点
记为 $a$ ， $a$ 就是直径的一端
从 $a$ $a$ 出发执行 $\textbf{bfs}(a)$ $bfs (a)$ ，求出最远的点 $b$ $b$ ，则 $(a, b)$ $(a, b)$ 为树的一条直径
- 在这个过程中，当每个点第一次被访问的时候，假如当前队列中取出 $x$
  对于边 $(x, y), \ vis[y] = 0$ ，可以实时维护前驱信息
  $\textbf{pre}(y) = x$
  最后从 $b$ 回到 $a$ ，可以得到具体的直径方案

codeforces1294F

$\textbf{bfs}(1)$ 并记录 $d$ 最远点， $a \leftarrow pos$
$\textbf{bfs}(a)$ 并记录 $d$ 信息
$da[\ ] \leftarrow d[\ ], \quad b \leftarrow pos$
$\textbf{bfs}(b)$ 并记录 $d$ 信息， $db[\ ] \leftarrow d[\ ]$

const int maxn = 400000 + 10;
int head[maxn], ne[maxn], ver[maxn], tot = 0, n, pos = 0;

void add(int x, int y) {
    ver[++tot] = y; ne[tot] = head[x]; head[x] = tot;
}

int da[maxn], db[maxn], d[maxn], vis[maxn];

void bfs(int u) {
    memset(d, 0, sizeof d);
    memset(vis, 0, sizeof vis);
    vis[u] = 1; d[u] = 0;
    queue<int> q;
    q.push(u);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (vis[y]) continue;

            vis[y] = 1;
            d[y] = d[x] + 1;
            if (d[y] > d[pos]) pos = y;
            q.push(y);
        }
    }
}

void solve() {
    bfs(1);
    int a = pos;

    bfs(a);
    int b = pos;
    memcpy(da, d, sizeof d);

    bfs(b);
    memcpy(db, d, sizeof d);

    int c = 0;
    for (int i = 1; i <= n; i++) {
        if (i == a || i == b) continue;
        if (da[i] + db[i] > da[c] + db[c]) c = i;
    }
    int res = (da[b] + db[c] + da[c]) / 2;
    printf("%d\n", res);
    printf("%d %d %d\n", a, b, c);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);

    // get data
    for (int i = 0; i < n-1; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }

    solve();
}

bfs 求树的直径比较适用于无边权，或者边的权值为 $1$ 的情况
bfs 求直径很容易求出直径的端点 $a, b$ 到树中其他各点的距离

树形 dp 求树的直径

treedp

void dp(int x) {
    vis[x] = 1;
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edges[i]);
        d[x] = max(d[x], d[y] + edges[i]);
    }
}

树的直径的综合应用（一）

Acwing350
Acwing350-01
Acwing350-02
diameter

const int maxn = 200000 + 10;
int head[maxn], edges[maxn], ver[maxn], ne[maxn], tot = 1;
int n, K;

void add(int x, int y, int z) {
    ver[++tot] = y; edges[tot] = z; ne[tot] = head[x]; head[x] = tot;
}

int vis[maxn], pre[maxn], d[maxn], pos;
void bfs(int u) {
    memset(vis, 0, sizeof vis);
    memset(pre, 0, sizeof pre);
    memset(d, 0, sizeof d);
    vis[u] = 1; d[u] = 0;
    queue<int> q; q.push(u);

    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            vis[y] = 1; d[y] = d[x] + edges[i];
            pre[y] = i;
            if (d[pos] < d[y]) pos = y;
            q.push(y);
        }
    }
}

void dp(int x, int &res) {
    vis[x] = 1;
    for (int i = head[x]; i; i = ne[i]) {
        int y = ver[i];
        if (vis[y]) continue;
        dp(y, res);
        res = max(res, d[x] + d[y] + edges[i]);
        d[x] = max(d[x], d[y] + edges[i]);
    }
}

void solve() {
    bfs(1);
    int a = pos;

    bfs(a);
    int ans = 2*(n-1) - (d[pos] - 1);
    if (K == 1) {
        printf("%d\n", ans);
        return;
    }

    // reverse path
    int u = pos;
    while (u) {
        int e = pre[u];
        edges[e] = edges[e^1] = -1;
        u = ver[e^1];
    }

    // dp
    memset(vis, 0, sizeof vis);
    memset(d, 0, sizeof d);
    int L = 0;
    dp(1, L);
    ans -= (L-1);
    printf("%d\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &K);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b, 1);
        add(b, a, 1);
    }

    // then solve
    solve();
}

树的直径的综合应用（二）

树网的核
很容易想到一种朴素算法，就是根据树网的核的定义，直接模拟

求出树的直径 $L$
枚举两个端点 $[p, q]$ ，保证 $q-p+1 \leqslant s$ ，线段 $[p, q]$ 是树网的核
模拟
- 对核 $\textbf{ker}$ 上的每个节点标记 $\textbf{vis}[\ ] = 1, D[\ ] = d[\ ] = 0$
- $\textbf{for} \ \forall u \in \bold{ker}, \textbf{dfs}(u)$ 或者 $\textbf{bfs}(u)$
  $\textbf{dfs}$ 的时候，可以求出核外的点 $x$ 与 $u$ 的距离 $d(x)$
  对于边 $(u, x)$ ，执行 $D(x) \leftarrow \min \{d(u) + e(u, x)\}$
- 遍历完成之后，对于 $\textbf{ker}$ 之外的每个节点 $x$
  $\forall x \notin \textbf{ker}$ ，此时 $D(x)$ 保存的就是节点 $x$ 到 $\bold{ker}$ 的距离
  $\forall x \notin \textbf{ker}$ ，对所有的 $D(x)$ 取最小值 $res$
- $ans \leftarrow \min \{res\}$ ，然后再检查其他的核
  最后 $ans$ 即为所求

Acwing351-01
Acwing351-02
Acwing351-03

编程小 tips
直径的方案可以用一个二元组 $(id, dist)$ 来保存到 $\textbf{path}[\cdots]$ 中
方便之后计算

const int maxn = 500000 + 10;
const int maxm = 1000000 + 5;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], edges[maxm], ne[maxm], tot = 1;
int n, s;

void add(int x, int y, int z) {
    ver[++tot] = y; edges[tot] = z; ne[tot] = head[x]; head[x] = tot;
}

int vis[maxn], pre[maxn], d[maxn];
void bfs(int u, int &pos) {
    memset(vis, 0, sizeof vis);
    memset(pre, 0, sizeof pre);
    memset(d, 0, sizeof d);
    vis[u] = 1; d[u] = 0;
    queue<int> q; q.push(u);

    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            vis[y] = 1;
            d[y] = d[x] + edges[i];
            pre[y] = x;
            if (d[y] > d[pos]) pos = y;
            q.push(y);
        }
    }
}

typedef pair<int, int> PII;
vector<PII> a;

int D[maxn];
int bfs_max(int u) {
    vis[u] = 1;
    queue<int> q;
    q.push(u);

    int res = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (vis[y]) continue;
            vis[y] = 1;
            d[y] = d[x] + edges[i];
            if (d[y] > res) res = d[y];
            q.push(y);
        }
    }
    return res;
}

void diameter() {
    int p = 0;
    bfs(1, p);
    int q = 0;
    bfs(p, q);

    while (q) {
        a.push_back({q, d[q]});
        q = pre[q];
    }
    reverse(a.begin(), a.end());

    // mark diameter
    memset(vis, 0, sizeof vis);
    for (auto x : a) vis[x.first] = 1;

    // get max dist out diameter
    memset(d, 0, sizeof d);
    for (auto x : a) D[x.first] = bfs_max(x.first);
    // for (int i = 1; i <= n; i++) printf("%d\n", D[i]);
}

void solve() {
    int q[maxn], l = 1, r = 0, ans = inf;
    for (int i = 0, j = 0; i < a.size(); i++) {
        while (a[i].second - a[j].second > s) j++;
        assert(j <= i);

        int res = max(a[j].second - a[0].second, a.back().second - a[i].second);
        while (l <= r && q[l] < j) l++;
        res = max(res, D[a[q[l]].first]);
        ans = min(ans, res);
        while (l <= r && D[a[q[r]].first] <= D[a[i].first]) r--;
        q[++r] = i;
    }
    printf("%d\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &s);
    for (int i = 0; i < n-1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); add(b, a, c);
    }

    // then diameter
    diameter();

    // solve
    solve();
}