填涂颜色

#include <iostream>
using namespace std;

// 因为 n <= 30，这里开 35 足够。
// 数组下标会用到 0 到 n + 1，所以要比 n 稍微大一点。
const int N = 35;

// a[i][j] 表示地图中的格子：
// 0 表示空白区域
// 1 表示闭合圈的边界
// -1 表示已经确定是“圈外”的 0
int a[N][N], n;

// 四个方向：右、左、上、下
// dx[i], dy[i] 配合使用，表示从当前位置走到相邻格子
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

// 判断坐标 (x, y) 是否在我们扩展后的地图范围内
// 原图范围是 1 ~ n
// 这里额外加了一圈边界，范围变成 0 ~ n + 1
bool inMap(int x, int y) {
    return x >= 0 && x <= n + 1 && y >= 0 && y <= n + 1;
}

// 从位置 (x, y) 开始进行 DFS 搜索
// 作用：把所有和“外部”连通的 0 都标记成 -1
void dfs(int x, int y) {
    // 枚举四个方向
    for(int i = 0; i < 4; i++) {
        // 计算相邻格子的坐标
        int nx = x + dx[i], ny = y + dy[i];

        // 如果相邻格子在地图范围内，并且它是 0，
        // 说明它和外部连通，需要标记为 -1
        if(inMap(nx, ny) && a[nx][ny] == 0) {
            // 标记为 -1，表示这是圈外的 0
            a[nx][ny] = -1;

            // 继续从这个格子往外扩展
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n;

    // 读入原始 n * n 方阵
    // 注意原图从下标 1 开始存储
    // 这样可以在外面留出一圈 0，方便从外部开始搜索
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];

    // 从扩展地图的左上角 (0, 0) 开始搜索
    // (0, 0) 一定在原图外部，所以从这里 DFS 可以找到所有圈外的 0
    a[0][0] = -1;
    dfs(0, 0);

    // 处理原图范围内的所有格子
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            // 如果是 -1，说明它是从外部能到达的 0
            // 输出时要恢复成 0
            if(a[i][j] == -1) a[i][j] = 0;

            // 如果仍然是 0，说明它没有被外部 DFS 搜到
            // 也就是说它被 1 围住了，是闭合圈内部的 0
            // 所以改成 2
            else if(a[i][j] == 0) a[i][j] = 2;

            // 输出当前格子
            // " \n"[j == n] 是一种简写：
            // 如果 j != n，输出空格；
            // 如果 j == n，输出换行。
            cout << a[i][j] << " \n"[j == n];
        }

    return 0;
}

观星

#include <iostream>
#include <set>
#include <map>
using namespace std;

// N, M 最大为 1500
// 这里开到 1505，防止边界越界
const int N = 1505;

// v[i][j] 表示星空矩阵中的字符
// '*' 表示当前位置有星星
// '.' 表示当前位置为空
char v[N][N];

// f[i][j] 表示当前位置是否已经被访问过
// true 表示访问过
// false 表示还没有访问过
bool f[N][N];

// n 表示行数，m 表示列数
int n, m;

// mp 用来统计每种“星座大小”对应的“星系大小”
// key：某个星座中星星的数量
// value：所有大小为 key 的星座包含的星星总数
//
// 例如：
// 有 3 个星座，它们的大小都是 4
// 那么 mp[4] = 12
map<int, int> mp;

// 八个方向
// 分别表示：上、右上、右、右下、下、左下、左、左上
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

// 从位置 (x, y) 开始 DFS
// 作用：找到与 (x, y) 相连的整个星座，并返回这个星座中星星的数量
int dfs(int x, int y) {
    // 当前这个位置本身就是一颗星星，所以初始数量为 1
    int cnt = 1;

    // 标记当前位置已经访问过
    // 防止之后重复访问同一颗星星
    f[x][y] = true;

    // 枚举当前位置周围的 8 个方向
    for(int i = 0; i < 8; i++) {
        // 计算相邻位置的坐标
        int nx = x + dx[i], ny = y + dy[i];

        // 判断这个相邻位置是否可以继续搜索：
        // 1. nx >= 0 && nx < n：行坐标没有越界
        // 2. ny >= 0 && ny < m：列坐标没有越界
        // 3. v[nx][ny] == '*'：这个位置上有星星
        // 4. f[nx][ny] == false：这个星星还没有被访问过
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && v[nx][ny] == '*' && f[nx][ny] == false)
            // 如果满足条件，说明这颗星星和当前星星属于同一个星座
            // 继续 DFS，并把搜索到的星星数量累加到 cnt 中
            cnt += dfs(nx, ny);
    }

    // 返回当前连通星座中星星的总数量
    return cnt;
}

int main() {
    // 输入星空矩阵的行数和列数
    cin >> n >> m;

    // 读入星空矩阵
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> v[i][j];

    // 枚举整个矩阵中的每一个位置
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            // 如果当前位置是星星，并且还没有被访问过，
            // 说明找到了一个新的星座
            if(v[i][j] == '*' && f[i][j] == false) {
                // DFS 求出这个星座中星星的数量
                int res = dfs(i, j);

                // 包含星星数量相同的星座属于同一个星系
                // 星系大小 = 这个星系中所有星座包含的星星总数
                //
                // 如果当前星座大小为 res，
                // 就把这个星座的 res 颗星星加入 mp[res]
                mp[res] += res;
            }

    // mp 中有多少个不同的 key，
    // 就说明有多少种不同大小的星座，
    // 也就是有多少个星系
    cout << mp.size() << ' ';

    // ans 用来记录最大的星系大小
    int ans = 0;

    // 遍历所有星系
    // it.first 是星座大小
    // it.second 是该星系的总大小
    for(auto it : mp)
        ans = max(ans, it.second);

    // 输出最大的星系大小
    cout << ans;

    return 0;
}

封锁阳光大学

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

int main() {
    // n 表示点数，m 表示边数
    // ans 表示最终答案：最少需要多少只河蟹
    // cnt 表示当前处理到了第几个连通块
    int n, m, ans = 0, cnt = 0;

    cin >> n >> m;

    // g[u] 存储和点 u 相邻的所有点
    // 因为是无向图，所以每条边要存两次
    vector<vector<int>> g(n + 1);

    // sta[i] 表示点 i 的染**况：
    // -1 表示还没有染色
    // 0 表示染成第 0 类
    // 1 表示染成第 1 类
    //
    // 这道题本质上要判断图是不是二分图。
    // 如果是二分图，那么每条边的两个端点一定在不同颜色集合中。
    vector<int> sta(n + 1, -1);

    // siz[k] 表示第 k 个连通块中一共有多少个点
    vector<int> siz(n + 1);

    // 读入所有道路
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        // 无向图，u 连 v，v 也连 u
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // dfs 用来给一个连通块染色，并统计其中一种颜色的点数
    //
    // 返回值含义：
    // 如果返回 -1，表示当前连通块不是二分图，无法满足要求
    // 否则返回当前连通块中 sta 为 1 的点数
    auto dfs = [&](auto &&self, int u) -> int {
        // res 初始为 sta[u]
        // 如果 sta[u] == 1，说明当前点属于颜色 1，贡献 1
        // 如果 sta[u] == 0，说明当前点属于颜色 0，贡献 0
        int res = sta[u];

        // 当前连通块的点数加 1
        siz[cnt]++;

        // 枚举点 u 的所有相邻点
        for(int v : g[u]) {
            // 如果相邻两个点颜色相同，
            // 说明这张图不是二分图。
            //
            // 因为如果两个相邻点都放河蟹，会冲突；
            // 如果要选一边作为封锁点，就必须能把图分成两边。
            if(sta[v] == sta[u]) return -1;

            // 如果点 v 还没有染色
            if(sta[v] == -1) {
                // 给 v 染成和 u 相反的颜色
                sta[v] = 1 - sta[u];

                // 继续 DFS 处理 v 所在的部分
                int tmp = self(self, v);

                // 如果子搜索发现不是二分图，直接向上传递 -1
                if(tmp == -1) return -1;

                // 把子树中颜色 1 的点数累加到 res
                res += tmp;
            }
        }

        // 返回当前连通块中颜色 1 的点数
        return res;
    };

    // 枚举所有点
    // 因为图不一定连通，所以要对每个连通块分别处理
    for(int i = 1; i <= n; i++) {
        // 如果这个点已经染过色，说明它所在的连通块已经处理过
        if(sta[i] != -1) continue;

        // 开始处理一个新的连通块
        // 先把当前点染成颜色 1
        sta[i] = 1;

        // 连通块编号加 1
        ++cnt;

        // 对这个连通块进行 DFS 染色
        // tmp 表示当前连通块中颜色 1 的点数
        int tmp = dfs(dfs, i);

        // 如果 tmp == -1，说明当前连通块不是二分图
        // 也就是说存在奇环，例如三角形
        //
        // 这种情况下无论怎么放河蟹，
        // 都无法做到既封锁所有道路，又不让相邻点同时放河蟹
        if(tmp == -1) {
            cout << "Impossible";
            return 0;
        }

        // 当前连通块一共有 siz[cnt] 个点
        // 颜色 1 的点数是 tmp
        // 颜色 0 的点数就是 siz[cnt] - tmp
        //
        // 对于一个二分图连通块：
        // 选颜色 1 的所有点，可以覆盖这个连通块中的所有边；
        // 选颜色 0 的所有点，也可以覆盖这个连通块中的所有边。
        //
        // 为了让河蟹数量最少，选择点数更少的那一边。
        ans += min(tmp, siz[cnt] - tmp);
    }

    // 输出最少需要的河蟹数量
    cout << ans << endl;

    return 0;
}

公共祖先

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

const int N = 2e5 + 5;

// g[u] 存储树上与 u 相邻的所有节点
vector<int> g[N];

// ans[r] 表示以 r 为根时，所有有序点对 (i, j) 的 LCA 编号之和
ll ans[N];

// cnt[u] 表示在以 1 为根时，节点 u 作为 LCA 出现的次数
// 注意这里统计的是有序点对 (i, j)
ll cnt[N];

// siz[u] 表示在以 1 为根时，u 的子树大小
ll siz[N];

// n 表示节点数量
ll n;

// 第一次 DFS：
// 1. 求出每个节点的子树大小 siz[u]
// 2. 求出以 1 为根时，每个节点 u 作为 LCA 出现的次数 cnt[u]
void dfs1(int u, int fa) {
    // 当前节点 u 本身算一个节点
    siz[u] = 1;

    // 遍历 u 的所有相邻节点
    for(auto v : g[u]) {
        // fa 是 u 的父节点，不能往回走
        if(v == fa) continue;

        // 先递归处理子节点 v
        dfs1(v, u);

        // 加上子树 v 的大小
        siz[u] += siz[v];

        // 如果两个点都在同一个儿子 v 的子树中，
        // 那么它们的 LCA 一定不会是 u，
        // 所以要减去 siz[v] * siz[v]
        //
        // 因为统计的是有序点对：
        // 第一个点有 siz[v] 种选法，
        // 第二个点也有 siz[v] 种选法，
        // 所以共有 siz[v] * siz[v] 对
        cnt[u] -= siz[v] * siz[v];
    }

    // siz[u] * siz[u] 表示：
    // 两个点都在 u 的子树中的有序点对数量
    //
    // 减去所有“两个点都在同一个儿子子树中”的情况后，
    // 剩下的点对，它们的 LCA 就是 u
    cnt[u] += siz[u] * siz[u];
}

int main() {
    cin >> n;

    // 读入 n - 1 条边
    // 因为是无根树，所以每条边要双向存储
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 先默认以 1 为根，计算 siz[u] 和 cnt[u]
    dfs1(1, 0);

    // 计算 ans[1]
    //
    // cnt[u] 表示以 1 为根时，u 作为 LCA 出现的次数
    // 每次出现都会贡献 u
    // 所以总贡献为 cnt[u] * u
    for(int u = 1; u <= n; u++)
        ans[1] += cnt[u] * u;

    // 接下来用换根思想，从 ans[1] 推出其他 ans[r]
    queue<int> q;
    q.push(1);

    // BFS 遍历整棵树
    // ans[x] 已经有值，表示 x 作为根时的答案已经算出来
    while(!q.empty()) {
        int u = q.front();
        q.pop();

        // 枚举 u 的相邻节点
        for(auto v : g[u]) {
            // 如果 ans[v] 已经被计算过，说明 v 已经访问过
            // 直接跳过，防止往回走
            if(ans[v]) continue;

            // 现在要从“以 u 为根”的答案推出“以 v 为根”的答案
            //
            // 设原来以 1 为根时，v 是 u 的儿子。
            // siz[v] 表示 v 这一侧的节点数量。
            //
            // 当根从 u 换到 v 时：
            // 对于跨过边 u-v 的点对：
            // 一个点在 v 子树内，另一个点在 v 子树外。
            //
            // 这些点对的 LCA 会从 u 变成 v。
            //
            // v 子树内有 siz[v] 个点，
            // v 子树外有 n - siz[v] 个点。
            //
            // 因为统计的是有序点对，所以数量是：
            // 2 * siz[v] * (n - siz[v])
            //
            // 每个这样的点对，LCA 编号从 u 变成 v，
            // 贡献变化量是 v - u。
            //
            // 所以总变化量为：
            // 2 * siz[v] * (n - siz[v]) * (v - u)
            ans[v] = ans[u] + 2 * siz[v] * (v - u) * (n - siz[v]);

            // 把 v 加入队列，继续向下换根
            q.push(v);
        }
    }

    // 按顺序输出每个节点作为根时的答案
    for(int i = 1; i <= n; i++)
        cout << ans[i] << ' ';

    return 0;
}