通讯网络

思路

假设总共 个城市构成了一棵树，任意一条边，都会将城市分成两部分，假设左边有 个，则右边有 个，那么左侧的每个城市和右侧的每个城市都会相连，即经过该边 次，一旦被破坏，造成的损失是 ，只需在dfs过程中取一下每条边贡献的最大值即可，时间复杂度 。

如下图所示：

Code

class Solution {
#define ll long long
#define maxn 100010
#define pii pair<int, int>
private:
    int n;
    int sz[maxn];  // sz[x] 表示结点 x 的子树结点数量
    ll ans;
    vector<pii> g[maxn];  // 保存边。

public:
    void dfs(int x, int fa = 0) {
        sz[x] = 1;
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            dfs(v, x);
            sz[x] += sz[v];
            ll tmp = 1ll * sz[v] * (n - sz[v]) * w;  // 计算该边对链路的影响
            ans = max(ans, tmp);
        }
    }

    ll solve(int n, vector<int> u, vector<int> v, vector<int> w) {
        this->n = n;
        for (int i = 1; i < n; ++i) {
            int a = u[i - 1], b = v[i - 1], c = w[i - 1];
            g[a].push_back({b, c});
            g[b].push_back({a, c});
        }
        dfs(1);
        return ans;
    }

};