AC代碼

https://codeforces.com/contest/1764/submission/184176192

題意：

Doremy有一個(gè)具有n個(gè)頂點(diǎn)的邊加權(quán)樹，其權(quán)重為1到10^9之間的整數(shù)。

她對(duì)其進(jìn)行了n(n+1)/2次實(shí)驗(yàn)。

在每個(gè)實(shí)驗(yàn)中，Doremy選擇頂點(diǎn)i和j，使得j≤i,然后連接頂點(diǎn)i和j，其邊權(quán)重為1.?

在圖中正好有一個(gè)循環(huán)（或當(dāng)i=j時(shí)的自循環(huán)）。

Doremy將f(i，j)定義為從每個(gè)頂點(diǎn)到循環(huán)的最短路徑的長(zhǎng)度之和。

形式上，設(shè)dis_(i，j)(x，y)是添加權(quán)重為1的邊（i，j）時(shí)頂點(diǎn)x和y之間的最短路徑的長(zhǎng)度，

S_(i，j)是添加邊（i、j）時(shí)在循環(huán)上的頂點(diǎn)集。然后

f(i，j)=∑x=1...n（min y∈S_(i，j)? dis_(i，j)(x，y)）。

Doremy記下f（i，j）的所有值，滿足1≤j≤i≤n. 給定f(i，j)的數(shù)值，你能幫她恢復(fù)樹嗎？

保證至少存在一棵合適的樹。

題解：

圖論

1. 求d[i][j],?1≤j≤i≤n,? 即任意兩個(gè)頂點(diǎn)之間的距離。

2. 在d[i][j],?1≤j≤i≤n, 基礎(chǔ)上求一棵最小生成樹。