給你一顆樹 每條邊有一個權值 選擇一個點為中心 定義S值為中心到其他n-1個點的路徑上的最小邊權 求所有點S值的和
從大到小排序 每次合並2棵樹 設為A集合 B集合 設A集合的最大S值的和為sumA B集合為sumB
中心在A或者B現在加入A-B這條邊使得2個集合連通 因為A-B這條邊的權值小於等於AB集合裡面邊的權值 所以如果合並之後中心在A 那麼sumA = sumA+B集合的點數*A-B這條邊的權值 sumB = sumB+A集合的點數*A-B這條邊的權值 2者取大
#include#include #include #include #include using namespace std; const int maxn = 200010; int n; int f[maxn], rank[maxn]; __int64 sum[maxn]; struct edge { int u, v, w; }e[maxn]; int find(int x) { if(x != f[x]) return f[x] = find(f[x]); return f[x]; } bool cmp(edge a, edge b) { return a.w > b.w; } int main() { while(scanf("%d", &n) != EOF) { for(int i = 0; i < n-1; i++) scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w); sort(e, e+n-1, cmp); for(int i = 0; i <= n; i++) f[i] = i, sum[i] = 0, rank[i] = 1; for(int i = 0; i < n-1; i++) { int x = find(e[i].u); int y = find(e[i].v); if(x != y) { if(sum[x]+(__int64)e[i].w*rank[y] > sum[y]+(__int64)e[i].w*rank[x]) { f[y] = x; sum[x] = sum[x]+(__int64)e[i].w*rank[y]; rank[x] += rank[y]; } else { f[x] = y; sum[y] = sum[y]+(__int64)e[i].w*rank[x]; rank[y] += rank[x]; } } } int x = find(1); printf("%I64d\n", sum[x]); } return 0; }