题意：给出一棵树，要求你加一条边，使得图上简单路径最多。
做法：
我们先刻画一下加一条边后路径个数是多少，发现只有对于两个点都不在环上且向环走最后到的节点相同，也就是在同一颗子树内的点没有增加路径。
那么我们回到树上，我们就等同于选择两个点之间连一条边，环即是这条边和他们在树上的路径所形成的环。我们记 \(f_u\) 为点 \(u\) 被选入路径后不向环上拓展的子树大小。那么我们假设选择的两个点为 \(x,y\)，稍微讨论就会发现答案应该长成这样：
解释一下为什么不考虑单点，因为在这种情况下，刚好每个单点都会被加一次减一次，不会有贡献。
既然是一个树上路径的东西，那么我们可以考虑枚举 lca 或者淀粉质，因为这里的信息比较简单我们考虑枚举 lca。
首先后面那一坨东西看着就很丑，我们考虑化成几个和式的形式。
假设 lca 为 \(u\)，注意到对于 \(u\) 在 \(x,y\) 方向上的链上的贡献都是 \((sz_{v} - sz_{son_{v}}) ^ 2\) 的形式，与上方无关，所以我们可以考虑直接 dp 出来，记每个子树内的最大的价值为 \(val_u\)。
那么考虑枚举 lca 为 \(u\)，首先第一种情况是我们直接连接 lca 和子树内的的一个点，这个就直接枚举是哪个儿子 \(v\)，然后直接计算 \((n-sz_v) ^2 + val_v\)，直接枚举即可。
问题在于第二种，我们有两个儿子，这个柿子为 \((n-sz_x-sz_y)^2+val_x+val_y\)，跟两个有关系。
我们考虑经典的处理手法，我们先将变量分离，发现跟 \(x,y\) 同时有关的是 \(2sz_xsz_y\)，那么我们可以枚举一个 \(x\) 去找出最优的对应的 \(y\)，发现这个东西是个一次函数状物，所以我们可以直接上斜率优化即可。
复杂度 \(O(n\log n)\)，瓶颈在于给儿子排序。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, mod = 998244353;
const double eps = 1e-8;
int n, sz[maxn], dp[maxn];
vector<int> e[maxn];
int X(int i) {return -2 * sz[i];
}
int Y(int i) {return dp[i] + sz[i] * sz[i] - 2 * n * sz[i];
}
double slope(int i, int j) {return (Y(j) - Y(i)) / (X(i) != X(j) ? X(j) - X(i) : eps);
}
int q[maxn], f, t;
void dfs1(int u, int fa) {sz[u] = 1;for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;dfs1(v, u);sz[u] += sz[v];}dp[u] = sz[u] * sz[u];for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;dp[u] = min(dp[u], dp[v] + (sz[u] - sz[v]) * (sz[u] - sz[v]));}
// cout << u << " " << dp[u] << endl;
}
int ans = 9e18;
bool cmp(int x, int y) {return sz[x] > sz[y];
}
void dfs2(int u, int fa) {sort(e[u].begin(), e[u].end(), cmp);ans = min(ans, dp[u] + (n - sz[u]) * (n - sz[u]));for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;dfs2(v, u);}f = t = 0;for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;while(f < t - 1 && slope(q[t - 2], q[t - 1]) < sz[v])f++;if(f < t) ans = min(ans, dp[q[f]] + dp[v] + (n - sz[q[f]] - sz[v]) * (n - sz[q[f]] - sz[v]));while(f < t - 1 && slope(q[t - 2], q[t - 1]) > slope(q[t - 1], v))t--;q[t++] = v;}
}
signed main() {cin >> n;for (int i = 1; i < n; i++) {int x, y; cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}dfs1(1, 0);dfs2(1, 0);cout << (n * (n - 1) + n * n - ans) / 2 << endl;return 0;
}