题意：有一颗n个节点的数，需要解决以下问题：
先去掉节点 v 和与其相连的边；然后在剩余的图上加若干条边，在 (x,y) 之间连边的代价是 ∣x−y∣。求使得图连通的最小代价。
计算删除顶点 v后，每个顶点 1≤v≤n至少需要花费多少金币才能使图形重新成为一棵树，以及需要添加哪些边。
做法：首先可以发现，因为每次只删除一个点，所以猜测连接每个联通块的代价不会大于2.
那么可以把 1 的代价和 2 的代价分开来考虑。
对于当前要删除点 v ,1 的代价又能分成两种情况，
第一种是 v 的子树和其父亲联通块相连的点对。
第二种是 v 的子树之间相连的点对。
先考虑怎么处理第一种情况的点对。
对于节点u 可能会有很多点对满足第一种情况
这些满足条件的点对（x,y）符合 |x-y|=1 且 dep[lca(x,y)]<dep[u].
但是我们只需要维护，所有点对里面 dep[lca(x,y)] 最小的那个就可以了。
具体做法就是 把所有差值为 1 的点对（x,y）和 其LCA 保存到 x 和 y 节点上。
当在我们在 dfs 时，先在当前 x 节点 能匹配的 y节点里能遇到的dep最小值和需要连接的 (x,y)这条边保存下来。然后再与子树中的 dep 做比较不断的更新.
通过这样处理，我们能得到在当前 x 节点下，能连接到 父亲连通块代价为1 的点对。
现在考虑怎么处理第二种情况的点对。
我的做法是把所有 (x,y) 放到其 lca(x,y)处。
然后在 dfs 的过程中处理以 X 为 lca 的点对。
这样就能保证这些点对就是 v的子树之间相连的。
在处理这个情况的时候会遇到一个问题，就是 x 节点属于哪个子树，这个是把 子树的 dfs 序进行排序，然后二分得到具体 x 节点属于哪个子树。
处理 2的代价与上述类似。
上述我们处理完这 4 类点对：
1.子树和其父亲连通块代价为 1 的
2.子树和子树之间代价为 1 的
3.子树和其父亲连通块代价为 2 的
4.子树和子树之间代价为 2 的
处理完这4种边以后呢，后续做法就是用并查集来维护连通块的信息。
我们先优连第2 类节点。然后在连第1 类节点，在连 3 ，4类节点。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pir;
const int N = 2e5 + 5;
const int INF = 1e9;
using Edge = int;
struct HLD
{
int n;
vector<int> sz, top, dep, fa, in, out, seq;
vector<vector<Edge> > g;
int ts;
HLD(const vector<vector<Edge> > &g, int root = 1) : n(int(g.size()) - 1), g(g)
{
ts = 0;
sz.resize(n + 1);
top.resize(n + 1);
dep.resize(n + 1);
fa.resize(n + 1);
in.resize(n + 1);
out.resize(n + 1);
seq.resize(n + 1);
dep[root] = 1;
top[root] = root;
dfs_sz(root);
dfs_hld(root);
}
void dfs_sz(int u)
{
if (fa[u])
{
for(auto it = g[u].begin(); it != g[u].end(); it++)
{
if (*it == fa[u])
{
g[u].erase(it);
break;
}
}
}
sz[u] = 1;
for(auto &j : g[u])
{
fa[j] = u;
dep[j] = dep[u] + 1;
dfs_sz(j);
sz[u] += sz[j];
if (sz[j] > sz[g[u][0]])
swap(j, g[u][0]);
}
}
void dfs_hld(int u)
{
in[u] = ++ts;
seq[in[u]] = u;
for (auto j : g[u])
{
top[j] = (j == g[u][0] ? top[u] : j);
dfs_hld(j);
}
out[u] = ts;
}
int lca(int u, int v)
{
while (top[u] != top[v])
{
if (dep[top[u]] > dep[top[v]])
{
u = fa[top[u]];
}
else
{
v = fa[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v)
{
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
bool in_subtree(int u, int v)
{
return in[v] <= in[u] && in[u] <= out[v];
}
int jump(int u, int k)
{
if (dep[u] < k)
{
return -1;
}
int d = dep[u] - k;
while (dep[top[u]] > d)
{
u = fa[top[u]];
}
return seq[in[u] - dep[u] + d];
}
int rooted_lca(int a, int b, int c)
{
return lca(a, b) ^ lca(b, c) ^ lca(c, a);
}
};
int f[N + 5], id[N + 5];
int leader(int x)
{
while (x != f[x]) x = f[x] = f[f[x]];
return x;
}
struct node
{
int u, v, x;
};
void solve()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)f[i] = i;
std::vector<vector<int>> g(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);
}
HLD hld(g);
std::vector<vector<pir>> Q(n + 1);
std::vector<vector<node>> add(n + 1);
for(int i = 1; i <= n; i++)
{
int u = i, v = i + 1;
if(v <= n)
{
if(!(hld.fa[u] == v || hld.fa[v] == u))
{
int L = hld.lca(u, v);
if(L == u || L == v)
{
}
else
{
Q[L].push_back({u, v});
}
add[u].push_back({u, v, L});
add[v].push_back({u, v, L});
}
}
}
std::vector<vector<pir>> Q2(n + 1);
std::vector<vector<node>> add2(n + 1);
for(int i = 1; i <= n; i++)
{
int u = i, v = i + 2;
if(v <= n)
{
if(!(hld.fa[u] == v || hld.fa[v] == u))
{
int L = hld.lca(u, v);
if(L == u || L == v)
{
}
else
{
Q2[L].push_back({u, v});
}
add2[u].push_back({u, v, L});
add2[v].push_back({u, v, L});
}
}
}
std::vector<vector<pir>> ans(n + 1);
std::vector<int> sum(n + 1);
std::vector<int>d1(n + 1, INF), d2(n + 1, INF);
std::vector<pir> ed_fa1(n + 1), ed_fa2(n + 1);
function<void(int, int)>dfs = [&](int u, int fa)
{
for(auto [x, y, z] : add[u])
{
if(hld.dep[z] < d1[u])
{
ed_fa1[u] = {x, y};
d1[u] = hld.dep[z];
}
}
for(auto [x, y, z] : add2[u])
{
if(hld.dep[z] < d2[u])
{
ed_fa2[u] = {x, y};
d2[u] = hld.dep[z];
}
}
for(int v : g[u])
{
if(v == fa)continue;
dfs(v, u);
if(d1[v] < d1[u])
{
ed_fa1[u] = ed_fa1[v];
d1[u] = d1[v];
}
if(d2[v] < d2[u])
{
ed_fa2[u] = ed_fa2[v];
d2[u] = d2[v];
}
}
int k = 0;
std::vector<pir> list;
for(int v : g[u])
{
if(v == fa)continue;
id[++k] = v;
list.push_back({hld.in[v], v});
}
if(k)
{
id[0] = N + 1;
sort(list.begin(), list.end());
for(auto [x1, y1] : Q[u])
{
int p1 = upper_bound(list.begin(), list.end(), pir{hld.in[x1], INF}) - list.begin() - 1;
int p2 = upper_bound(list.begin(), list.end(), pir{hld.in[y1], INF}) - list.begin() - 1;
int x = list[p1].second, y = list[p2].second;
if(leader(x) == leader(y))continue;
f[leader(y)] = f[leader(x)];
ans[u].push_back({x1, y1});
sum[u]++;
}
for(int i = 1; i <= k; i++)
{
int v = id[i];
if(leader(v) == leader(id[0]))continue;
if(d1[v] < hld.dep[u])
{
f[leader(v)] = f[leader(id[0])];
ans[u].push_back({ed_fa1[v].first, ed_fa1[v].second});
sum[u]++;
}
}
for(int i = 1; i <= k; i++)
{
int v = id[i];
if(leader(v) == leader(id[0]))continue;
if(d2[v] < hld.dep[u])
{
f[leader(v)] = f[leader(id[0])];
ans[u].push_back({ed_fa2[v].first, ed_fa2[v].second});
sum[u] += 2;
}
}
for(auto [x1, y1] : Q2[u])
{
int p1 = upper_bound(list.begin(), list.end(), pir{hld.in[x1], INF}) - list.begin() - 1;
int p2 = upper_bound(list.begin(), list.end(), pir{hld.in[y1], INF}) - list.begin() - 1;
int x = list[p1].second, y = list[p2].second;
if(leader(x) == leader(y))continue;
f[leader(y)] = f[leader(x)];
ans[u].push_back({x1, y1});
sum[u] += 2;
}
for(int i = 1; i <= k; i++)f[id[i]] = id[i];
}
};
dfs(1, 0);
for(int i = 1; i <= n; i++)
{
cout << sum[i] << " " << ans[i].size() << endl;
for(auto [x, y] : ans[i])cout << x << " " << y << endl;
cout << '\n';
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int t;
cin >> t;
while(t--)
{
solve();
}
}
/*
*/