題目描述Kagari 正準(zhǔn)備對一棵樹進(jìn)行歸檔她知道歸檔的成本取決于樹的直徑 1。為了降低成本她的目標(biāo)是首先盡可能縮小直徑。她可以對樹執(zhí)行以下操作選擇兩個(gè)頂點(diǎn) s 和 t。設(shè)從 s 到 t 的簡單路徑 2 上的頂點(diǎn)序列為 v0?,v1?,…,vk?其中 v0?s,vk?t。 移除路徑上的所有邊。即移除邊 (v0?,v1?),(v1?,v2?),…,(vk?1?,vk?)。將頂點(diǎn) v1?,v2?,…,vk? 直接連接到 v0?。即添加邊 (v0?,v1?),(v0?,v2?),…,(v0?,vk?)。可以證明操作后圖仍然是一棵樹。請幫助她確定實(shí)現(xiàn)最小直徑所需的最少操作次數(shù)。注釋1 樹的直徑是任意兩個(gè)頂點(diǎn)之間可能的最長距離。距離本身通過連接它們的唯一簡單路徑上的邊數(shù)來衡量。2 簡單路徑是樹中兩個(gè)頂點(diǎn)之間的路徑且不會重復(fù)訪問任何頂點(diǎn)?？梢宰C明任意兩個(gè)頂點(diǎn)之間的簡單路徑總是唯一的。輸入格式每個(gè)測試包含多個(gè)測試用例。第一行包含測試用例的數(shù)量 t(1≤t≤104)。每個(gè)測試用例的第一行包含一個(gè)整數(shù) n(2≤n≤2?105)表示樹中頂點(diǎn)的數(shù)量。每個(gè)測試用例的接下來 n?1 行描述樹。每行包含兩個(gè)整數(shù) u 和 v(1≤u,v≤n,uv)表示頂點(diǎn) u 和 v 之間有一條邊。保證這些邊構(gòu)成一棵樹。保證所有測試用例的 n 之和不超過 2?105。輸出格式對于每個(gè)測試用例輸出一個(gè)整數(shù)表示實(shí)現(xiàn)最小直徑所需的最少操作次數(shù)。輸入輸出樣例輸入 #1復(fù)制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復(fù)制1 0 0 4說明/提示在第一個(gè)測試用例中原始樹的直徑為 3。Kagari 可以對 s3 和 t4 執(zhí)行操作。操作包括以下步驟移除邊 (3,1), (1,2) 和 (2,4)。添加邊 (3,1), (3,2) 和 (3,4)。操作后直徑減小到 2?？梢宰C明 2 是最小直徑。在第二個(gè)測試用例中樹的直徑為 1。 可以證明 1 已經(jīng)是最小值因此 Kagari 無需執(zhí)行操作。每次操作選擇兩個(gè)頂點(diǎn) s 和 t。設(shè)從 s 到 t 的簡單路徑 2 上的頂點(diǎn)序列為 v0?,v1?,…,vk?其中 v0?s,vk?t。 移除路徑上的所有邊。即移除邊 (v0?,v1?),(v1?,v2?),…,(vk?1?,vk?)。將頂點(diǎn) v1?,v2?,…,vk? 直接連接到 v0?。即添加邊 (v0?,v1?),(v0?,v2?),…,(v0?,vk?)。即把一條鏈“壓扁”成以起點(diǎn)為中心的星形。#include bits/stdc.h #define int long long using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //這個(gè)記得注釋掉 //freopen(../input.txt,r,stdin); int t; cint; while (t--) { //cout------------------------\n; int n; cinn; vectorvectorintg(n1); vectorintin(n1);//記錄每個(gè)點(diǎn)連了多少個(gè)點(diǎn) for (int i1;in-1;i) { int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); in[u]; in[v]; } //統(tǒng)計(jì)整棵樹有多少個(gè)葉子 int cnt_leaf0; for (int i1;in;i) { //度數(shù)為 1 的節(jié)點(diǎn)就是葉子 if (in[i]1) cnt_leaf; } //找直連葉子最多的點(diǎn)作為根 int max_leaf0; for (int u1;un;u) { //當(dāng)前葉子u周圍直接連著幾個(gè)葉子 int cur_leaf0; for (int v:g[u]) { //度數(shù)為 1 的節(jié)點(diǎn)就是葉子 if (in[v]1) cur_leaf; } if (cur_leafmax_leaf) max_leafcur_leaf; } //葉子總數(shù)-已經(jīng)直連當(dāng)前中心的葉子數(shù) int anscnt_leaf-max_leaf; if (n2)//特判 ans0; coutans\n; } return 0; }