題目：http://www.51nod.com/onlineJudge/questionCode.html#!PRoblemId=1737

題意：

給出一棵n個(gè)點(diǎn)的樹，將這n個(gè)點(diǎn)兩兩配對，求所有可行的方案中配對兩點(diǎn)間的距離的總和最大為多少。

分析：

貪心的想，為使距離總和最大，每條邊乘上的系數(shù)就要盡量的大， 設(shè)fx表示點(diǎn)x的兒子個(gè)數(shù)，那每一條邊能乘上的最大的系數(shù)，就是：min(n?fx,fx) 這種貪心的方法是否存在于一種構(gòu)造方法呢？ 構(gòu)造：找出樹的重心，只要保證刪去重心后任意同一聯(lián)通塊中的兩點(diǎn)不構(gòu)成路徑即可，這樣每個(gè)連通塊中的點(diǎn)都向其他連通塊中的點(diǎn)連接，這樣構(gòu)造出來的配對方案滿足了每條邊都被統(tǒng)計(jì)min(s1,s2)次。 （找重心是為了每個(gè)連通塊不能超過n/2個(gè)點(diǎn)，其實(shí)只要最大連通塊不超過n/2個(gè)點(diǎn)，就能構(gòu)造出一種配對方案使得每條邊被統(tǒng)計(jì)min(s1,s2)次。） 時(shí)間復(fù)雜度O(n)

代碼：