题解 | #通讯网络#

思路：

题目的主要信息：

• n个节点，n-1条边，使之全部连通，这就是一棵树
• 权值就是通话质量，任意去掉一条边，求影响的最大的通话质量（有n个城市受影响，就要用n乘上去掉边的权值）
  

即影响的城市数为去掉边后两个子树节点数相乘，因此我们找到，其中是去掉权值为的边后子树的节点数。

这道题需要求子树的节点数，只能用递归的dfs，自底向上相加，不能用bfs，也无法用非递归dfs，因为非递归dfs无法自底向上，这是树而不是二叉树。

方法：递归深度优先搜索
具体做法：
我们可以用深度优先搜索（dfs)的方式遍历树的每一条边，计算上述公式，找到最大值。因为深度优先搜索是自底向上的，因此节点数刚好可以累加。

class Solution {
public:
    vector<pair<int, int> > vec[100020]; //连接两个节点
    long long res;
    int sz[100020]; //统计子树节点数
    void dfs(int x, int pre, int n){ //x为当前节点，pre为前一个节点
        sz[x] = 1;
        for(int i = 0; i < vec[x].size(); i++){//遍历该节点每条边
            if(vec[x][i].first == pre)
                continue;
            dfs(vec[x][i].first, x, n); //向深处遍历
            sz[x] += sz[vec[x][i].first]; //计算子树和
            long long temp = sz[vec[x][i].first] * (n - sz[vec[x][i].first]) * vec[x][i].second;
            res = max(res, temp); //维护最大值
        }
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        for(int i = 0; i < u.size(); i++){ //建立邻近矩阵
            vec[u[i]].push_back(make_pair(v[i], w[i]));
            vec[v[i]].push_back(make_pair(u[i], w[i]));
        }
        dfs(1, 0, n);
        return res;
    }
};

复杂度分析：

• 时间复杂度：，遍历每个树的每个节点，只遍历一次
• 空间复杂度：，辅助数组vec最坏为邻接矩阵