HDU 4424 Conquer a New Region：並查集維護邊權最小值的最大生成樹應用

HDU 4424 Conquer a New Region：並查集維護邊權最小值的最大生成樹應用

問題描述

給定一棵樹，邊有權值。從某點出發，路徑價值 = 路徑上邊權最小值。求出發點使所有點路徑價值之和最大。

核心洞察

按邊權從大到小加入並查集。當加入邊 (u,v,w) 時，連接兩個連通塊 A,B。
若在 A 選點，新增貢獻 = w × |B|（B 中所有點經此邊到達 A，瓶頸為 w）。
同理在 B 選點貢獻 = w × |A|。
取較大者作為新連通塊的「最佳出發點貢獻和」。

算法流程

1. 邊按權值降序排序
2. 初始化：每點獨立集合，size=1, dis=0
3. 遍歷邊：合併兩集合，dis[new] = max(dis[A] + w*size[B], dis[B] + w*size[A])
4. 最終答案 = 整棵樹合併後的 dis[root]

完整 AC 代碼

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
#define MAX 200010

struct Edge { int u, v, w; } a[MAX];
long long dis[MAX];
int fa[MAX], sz[MAX];

bool cmp(Edge a, Edge b) { return a.w > b.w; }

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void unite(int x, int y, long long val) {
    fa[x] = y; sz[y] += sz[x]; dis[y] = val;
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i < n; i++) scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
        for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; dis[i] = 0; }
        sort(a+1, a+n, cmp);
        for (int i = 1; i < n; i++) {
            int f1 = find(a[i].u), f2 = find(a[i].v);
            if (f1 != f2) {
                long long s1 = dis[f1] + 1LL * a[i].w * sz[f2];
                long long s2 = dis[f2] + 1LL * a[i].w * sz[f1];
                if (s1 > s2) unite(f2, f1, s1);
                else unite(f1, f2, s2);
            }
        }
        printf("%lld\n", dis[find(1)]);
    }
    return 0;
}

關鍵點

• 樹無環，並查集合併無需判環
• dis[x] 存儲以該集合最佳點為根的總貢獻和
• 長長整型防溢出