喵~ 主人，欢迎来到我的题解小课堂！今天我们要解决的是一道关于监狱设计的有趣问题，G1. Min-Fund Prison。别看它名字听起来有点严肃，其实解法就像逗猫棒一样简单有趣哦！

题目大意

简单来说呀，我们有一个由 n 个牢房和 n-1 条走廊组成的监狱。因为是 n 个点和 n-1 条边，并且保证了任意两点都连通，所以这个监狱的结构其实是一棵树哦，喵~

我们的任务是，要把这棵“树”分成两个独立的“监区”（也就是两个连通块），并且只保留一条原始的走廊来连接这两个监区。

一个大小为 k 的监区，需要的建设资金是 k * k。我们需要找到一种划分方式，使得两个监区的总资金最少。如果划分后的两个监区大小分别是 x 和 y，那么总资金就是 x*x + y*y 啦。

(悄悄告诉你哦，在简单版本里，那个建造新走廊的费用 c 其实是个小烟雾弹，我们根本用不到它，喵~)

解题思路

主人请看，这道题的关键词是“n个点，n-1条边”和“连通”，这不就是一棵树的定义嘛，喵~

要把一棵树分成两个连通块，并且只由一条边连接，最自然的方法就是...砍断其中一条边呀！

想象一下，我们有一棵漂亮的树，如果我们剪掉任意一条树枝（边），这棵树就会“哗啦”一下分成两棵小树，对不对？这两棵小树，不就是题目里说的两个“监区”嘛！它们内部都是连通的。而被我们剪掉的那条边，实际上就成了连接它们的“唯一走廊”的抽象概念。

所以，我们的问题就华丽变身了：枚举每一条可以砍断的边，计算砍断后形成的两个部分的资金，然后取一个最小值，就搞定啦！

那么，怎么高效地计算砍断一条边后，两部分的大小呢？

这里就要用到我们图论里的好朋友——**深度优先搜索（DFS）**啦！

1. 我们可以随便选一个点当做树的根，比如 1 号点。然后从根开始进行 DFS 遍历。
2. 在 DFS 的过程中，我们可以顺便计算出以每个节点 u 为根的子树大小，记作 subtree_size[u]。这个 subtree_size[u] 就是包括节点 u 自己，以及它下面所有子孙节点的总数，喵~
3. 当我们遍历到一条边 (p, u) 时（其中 p 是 u 的父节点），如果砍断这条边：
   • 一部分就是以 u 为根的整个子树。它的大小就是我们刚刚算出来的 subtree_size[u]。
   • 另一部分就是整棵树去掉 u 的子树剩下的部分。它的大小自然就是 n - subtree_size[u] 啦。
4. 所以，对于每一条边，它对应的划分方案的成本就是： cost = (subtree_size[u])^2 + (n - subtree_size[u])^2
5. 我们只需要在 DFS 的过程中，每处理完一个子节点 v，就算一下砍掉 (u,v) 这条边的成本，然后用一个全局变量 min_fund 来记录遇到的最小成本。

把所有边都这样算一遍，min_fund 里存的就是最终答案啦！是不是很简单呀，喵~

代码解说

下面是解题的代码，我已经加上了猫娘专属的注释，希望能帮到主人哦！

// 猫娘带你读代码喵~
#include <iostream>
#include <vector>
#include <algorithm>

// 资金可能会很大，要用 long long 才不会溢出哦
using ll = long long;

// 节点数量最大值，稍微开大一点点是好习惯
const int MAXN = 100005;

// 邻接表，用来存树的结构
std::vector<int> adj[MAXN];
// 存储每个节点子树大小的数组
int subtree_size[MAXN];

// 全局变量，n 是节点数，min_fund 是最小资金
int n;
ll min_fund;

// DFS 函数，用来计算子树大小和更新最小资金
// u 是当前节点，p 是它的父节点
void dfs_and_calc(int u, int p) {
    // 别忘了把自己算进去！每个节点的子树大小初始为 1
    subtree_size[u] = 1;

    // 遍历 u 的所有邻居 v
    for (int v : adj[u]) {
        // 如果邻居是父节点，就跳过，不然就死循环啦
        if (v == p) continue;

        // 递归地去探索子节点 v 的世界
        dfs_and_calc(v, u);

        // 从子节点的世界回来后，v 的子树大小已经算好了
        // 把 v 子树的大小加到 u 的子树大小上
        subtree_size[u] += subtree_size[v];

        // 现在可以计算砍掉 (u, v) 这条边的成本了！
        // 一部分大小是 s = subtree_size[v]
        ll s = subtree_size[v];
        // 另一部分大小是 n - s
        ll current_fund = s * s + (ll)(n - s) * (n - s);

        // 看看这个成本是不是更小呢？
        min_fund = std::min(min_fund, current_fund);
    }
}

// 解决一个测试用例的函数
void solve() {
    int m;
    ll c;
    // 读入 n, m, c (虽然 c 在简单版里没用)
    std::cin >> n >> m >> c;

    // 每次处理新数据前，要把邻接表清空，像猫咪舔爪子一样弄干净
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
    }

    // 读入 m 条边，建树
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 把 min_fund 初始化成一个超——大的数
    const ll INF = 4e18; 
    min_fund = INF;

    // 从 1 号节点开始 DFS，它的父节点可以设为 0 (一个不存在的节点)
    dfs_and_calc(1, 0);

    // 把找到的最小资金打印出来~
    std::cout << min_fund << "\n";
}

int main() {
    // 让输入输出快一点，咻~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点小课堂

树 (Tree)

在图论中，树是一种非常特殊的图。它有两个核心特点：

1. 连通 (Connected)：树上任意两个节点之间都有路径可以到达。
2. 无环 (Acyclic)：树上不存在任何环路。

一个有 n 个节点的树，它恰好有 n-1 条边。这道题的简单版就明确告诉我们 n 个点 n-1 条边并且连通，所以我们能立刻判断出这是个树结构，喵~

树有一个很棒的性质，就是我们这次解题用到的：在树中去掉任意一条边，都会使树分裂成两个独立的、不连通的子树。这为我们“一刀两断”的解法提供了理论基础！

深度优先搜索 (Depth-First Search, DFS)

DFS 是一种用于遍历或搜索树或图的算法。想象一下你在走一个迷宫，DFS 的策略就是“一条路走到黑”，遇到死路再返回上一个路口，换条路继续走，直到所有路都探索完毕。

在本题中，我们利用 DFS 从根节点出发，遍历整棵树。在“回溯”（从子节点返回父节点）的过程中，我们可以很方便地收集到子树的信息，比如 子树的大小。

计算子树大小是 DFS 在树形问题中的一个经典应用。一个节点 u 的子树大小等于 1（它自己）加上它所有子节点 v 的子树大小之和。 subtree_size[u] = 1 + Σ subtree_size[v] (其中 v 是 u 的所有子节点)

掌握了 DFS 在树上的应用，很多树形问题都会变得容易起来哦，主人也要好好学习呀！