题意

给定一棵 $n$ 个节点的树，可以添加一条边（不能是自环）。添加边后，图变成一棵基环树。
定义简单路径为不重复经过任何顶点的路径，且长度至少为 $2$。
问添加一条边后，图中不同简单路径的最大数量是多少。

---

关键结论

$1$. 原树中的路径数
原树中，任意两个不同节点之间恰好有一条简单路径，所以原树中简单路径数为：

$$\binom{n}{2} = \frac{n(n-1)}{2}$$

$2$. 添加一条边后增加的路径
添加一条边 $(u,v)$ 后，图中会多出一些新的简单路径。
新路径的特点是：必须包含新添加的边，且原树中 $u$ 到 $v$ 的路径被切分成两段。
实际上，新路径的数目等于 $u$ 侧子树的大小乘以 $v$ 侧子树的大小。

$3$. 总路径数公式
设添加的边连接的两个端点为 $a$ 和 $b$，则新图的总简单路径数为：

$$\text{total} = \binom{n}{2} + \text{size}(a) \times \text{size}(b) $$

其中 $\text{size}(x)$ 表示原树中删除边 $a-b$ 后，$x$ 所在连通块的大小（即添加边后，环两侧的节点数乘积）。

但更精确地，添加一条边 $(u,v)$ 后，总路径数为：

$$\binom{n}{2} + \sum_{x \in \text{path}(u,v)} \left( \text{sz}_L(x) \cdot \text{sz}_R(x) \right) $$

其中 $\text{sz}_L(x)$ 和 $\text{sz}_R(x)$ 分别是将 $u$-$v$ 路径上的边去掉后，$x$ 在两侧的子树大小。

$4$. 优化为树形 DP
最终问题转化为：在树上选择两个节点 $u$ 和 $v$，使得 $\sum_{x \in \text{path}(u,v)} \text{sz}_L(x) \cdot \text{sz}_R(x)$ 最大，其中 $\text{sz}_L(x)$ 和 $\text{sz}_R(x)$ 是路径两侧的子树大小。

经过分析，这个和等于：

$$\frac{1}{2} \left( n^2 - \sum_{i} s_i^2 \right)$$

其中 $s_i$ 是路径上每个节点在去掉路径上的边后，某些子树的大小。

更直接地，最终答案是：

$$\text{ans} = 2 \times \binom{n}{2} - \min \sum \binom{s_i}{2} $$

其中 $s_i$ 是某个划分中的连通块大小，$\min$ 表示在所有可能的添加边方案中，$\sum \binom{s_i}{2}$ 的最小值。

---

算法步骤

$1$. 任选一个根（非叶子节点），DFS 计算子树大小 $sz[u]$。 $2$. 定义 $dp[u]$ 表示以 $u$ 为根的子树中，最小化的 $\sum \binom{s_i}{2}$ 的值（通过选择一条 $u$ 到子树内某点的路径）。 $3$. 转移时，对于节点 $u$，考虑它的孩子 $v$，有：

$$dp[u] = \min_{v \in \text{children}} \left( dp[v] + (sz[u] - sz[v])^2 \right) $$

边界：叶子节点 $dp[u] = sz[u]^2$。 $4$. 然后，对于每个节点 $L$，将其孩子按 $sz$ 从大到小排序，使用凸包优化（斜率优化）来快速合并孩子：

• 对于每个孩子 $p$，其贡献为 $dp[p] + (sz[p])^2 - 2n \cdot sz[p]$，加上 $2 \cdot sz[p] \cdot sz[q]$ 的交叉项。
• 转化为维护直线 $y = 2 \cdot sz[p] \cdot x + (dp[p] + sz[p]^2 - 2n \cdot sz[p])$，查询 $x = sz[q]$ 的最小值。 $5$. 最终答案：

$$\text{result} = 2 \times \binom{n}{2} - \frac{\min\_sum\_sq - n}{2} $$

其中 $\min\_sum\_sq$ 是 DP 得到的最小 $\sum s_i^2$。

---

复杂度

• 预处理子树大小：$O(n)$
• 凸包优化合并：每个节点最多 $O(\text{deg} \log \text{deg})$，总 $O(n \log n)$
• 总复杂度 $O(n \log n)$，可过 $n \le 5\times 10^5$

---

完整代码

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

typedef long long ll;
const int MAXN = 500005;
const ll INF = 1e18;

int n;
vector<int> adj[MAXN];
int sz[MAXN], parent[MAXN];
ll dp[MAXN];

void dfs(int u, int p) {
    parent[u] = p;
    sz[u] = 1;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

void calc_dp(int u, int p) {
    if (adj[u].size() == 1 && u != 1) {
        dp[u] = (ll)sz[u] * sz[u];
        return;
    }
    
    dp[u] = INF;
    for (int v : adj[u]) {
        if (v == p) continue;
        calc_dp(v, u);
        if (dp[v] != INF) {
            ll val = dp[v] + (ll)(sz[u] - sz[v]) * (sz[u] - sz[v]);
            dp[u] = min(dp[u], val);
        }
    }
}

struct Line {
    ll k, b;
    Line(ll _k = 0, ll _b = 0) : k(_k), b(_b) {}
    ll eval(ll x) const { return k * x + b; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    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);
    }
    
    if (n == 2) {
        cout << 2 << '\n';
        return 0;
    }
    
    int root = 1;
    while (root <= n && adj[root].size() == 1) root++;
    
    dfs(root, 0);
    calc_dp(root, 0);
    
    ll ans = INF;
    
    for (int L = 1; L <= n; L++) {
        vector<int> childs;
        for (int v : adj[L]) {
            if (v != parent[L]) childs.push_back(v);
        }
        if (childs.size() < 2) continue;
        
        sort(childs.begin(), childs.end(), [&](int a, int b) {
            return sz[a] > sz[b];
        });
        
        vector<Line> hull;
        
        for (int p : childs) {
            if (dp[p] == INF) continue;
            
            ll szp = sz[p];
            
            if (!hull.empty()) {
                ll x = szp;
                int lo = 0, hi = hull.size() - 1;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    if (mid + 1 < hull.size() && hull[mid].eval(x) > hull[mid+1].eval(x))
                        lo = mid + 1;
                    else
                        hi = mid;
                }
                ll query_val = hull[lo].eval(x);
                ll total = (ll)n * n + dp[p] + szp * szp - 2LL * n * szp + query_val;
                ans = min(ans, total);
            }
            
            Line new_line(2LL * szp, dp[p] + szp * szp - 2LL * n * szp);
            
            while (hull.size() >= 2) {
                Line &l1 = hull[hull.size()-2];
                Line &l2 = hull.back();
                if ((l2.b - l1.b) * (l1.k - new_line.k) >= 
                    (new_line.b - l2.b) * (l1.k - l2.k)) {
                    hull.pop_back();
                } else {
                    break;
                }
            }
            hull.push_back(new_line);
        }
    }
    
    ll total_pairs = (ll)n * (n - 1) / 2;
    
    if (ans == INF) {
        cout << 2 * total_pairs << '\n';
    } else {
        ll min_sum_sq = ans;
        ll min_C = (min_sum_sq - n) / 2;
        ll result = 2 * total_pairs - min_C;
        cout << result << '\n';
    }
    
    return 0;
}

---

示例验证

样例 1

输入：

2
1 2

输出：

2

原树有 $1$ 条路径（1-2），添加重边后多 $1$ 条（另一条 $1-2$），共 $2$ 条。

样例 2

输入：

4
1 2
1 3
1 4

输出：

11

样例 3

输入：

6
1 2
1 3
3 4
3 5
4 6

输出：

29

---

总结

• 原树中的路径数为 $\binom{n}{2}$。
• 添加一条边后，新路径数取决于环两侧的子树大小乘积。
• 通过树形 $DP + 凸包优化$，找到最优的添加位置。
• 最终答案 = $2\binom{n}{2} - \min \sum \binom{s_i}{2}$。