CF2131D Arboris Contractio

题目描述Kagari 正准备对一棵树进行归档她知道归档的成本取决于树的直径 ¹。为了降低成本她的目标是首先尽可能缩小直径。她可以对树执行以下操作选择两个顶点 s 和 t。设从 s 到 t 的简单路径 ² 上的顶点序列为 v0​,v1​,…,vk​其中 v0​s,vk​t。 移除路径上的所有边。即移除边 (v0​,v1​),(v1​,v2​),…,(vk−1​,vk​)。将顶点 v1​,v2​,…,vk​ 直接连接到 v0​。即添加边 (v0​,v1​),(v0​,v2​),…,(v0​,vk​)。可以证明操作后图仍然是一棵树。请帮助她确定实现最小直径所需的最少操作次数。注释¹ 树的直径是任意两个顶点之间可能的最长距离。距离本身通过连接它们的唯一简单路径上的边数来衡量。² 简单路径是树中两个顶点之间的路径且不会重复访问任何顶点。可以证明任意两个顶点之间的简单路径总是唯一的。输入格式每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。每个测试用例的第一行包含一个整数 n(2≤n≤2⋅105)表示树中顶点的数量。每个测试用例的接下来 n−1 行描述树。每行包含两个整数 u 和 v(1≤u,v≤n,uv)表示顶点 u 和 v 之间有一条边。保证这些边构成一棵树。保证所有测试用例的 n 之和不超过 2⋅105。输出格式对于每个测试用例输出一个整数表示实现最小直径所需的最少操作次数。输入输出样例输入 #1复制4 4 1 2 1 3 2 4 2 2 1 4 1 2 2 3 2 4 11 1 2 1 3 2 4 3 5 3 8 5 6 5 7 7 9 7 10 5 11输出 #1复制1 0 0 4说明/提示在第一个测试用例中原始树的直径为 3。Kagari 可以对 s3 和 t4 执行操作。操作包括以下步骤移除边 (3,1), (1,2) 和 (2,4)。添加边 (3,1), (3,2) 和 (3,4)。操作后直径减小到 2。可以证明 2 是最小直径。在第二个测试用例中树的直径为 1。 可以证明 1 已经是最小值因此 Kagari 无需执行操作。每次操作选择两个顶点 s 和 t。设从 s 到 t 的简单路径 ² 上的顶点序列为 v0​,v1​,…,vk​其中 v0​s,vk​t。 移除路径上的所有边。即移除边 (v0​,v1​),(v1​,v2​),…,(vk−1​,vk​)。将顶点 v1​,v2​,…,vk​ 直接连接到 v0​。即添加边 (v0​,v1​),(v0​,v2​),…,(v0​,vk​)。即把一条链“压扁”成以起点为中心的星形。#include bits/stdc.h #define int long long using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //这个记得注释掉 //freopen(../input.txt,r,stdin); int t; cint; while (t--) { //cout------------------------\n; int n; cinn; vectorvectorintg(n1); vectorintin(n1);//记录每个点连了多少个点 for (int i1;in-1;i) { int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); in[u]; in[v]; } //统计整棵树有多少个叶子 int cnt_leaf0; for (int i1;in;i) { //度数为 1 的节点就是叶子 if (in[i]1) cnt_leaf; } //找直连叶子最多的点作为根 int max_leaf0; for (int u1;un;u) { //当前叶子u周围直接连着几个叶子 int cur_leaf0; for (int v:g[u]) { //度数为 1 的节点就是叶子 if (in[v]1) cur_leaf; } if (cur_leafmax_leaf) max_leafcur_leaf; } //叶子总数-已经直连当前中心的叶子数 int anscnt_leaf-max_leaf; if (n2)//特判 ans0; coutans\n; } return 0; }