题目理解

n个城市对应n个结点，城市之间的路径对应结点之间的边。我们删除某一条边。假设有m条两点之间的路径经过该边，该边的权值为w[i]，输出为m*w[i]的最大值。

方法一

对于题意的理解，我们删除一条边，其权重为w[i]；如果在原来的图中，有m条路径包含了该边，则最后输出代价为w[i]*m。那m是多少呢？

n个城市，n-1条边，意味着这是一个树的结构，图中不存在回路。因此，删除一条边会将树分为两个不连通的子树a,b，即可以把删除的边看作原来a,b之间的桥梁。a中结点到b中结点的路径必然包含了桥梁。所以说，m = a的结点个数*b的结点个数。

示意图如下（以删除3-6之间的边为例，子树a包含1、4、5、6、7，子树b包含2、3）：

我们先用邻接矩阵存储边和结点的信息。
然后遍历每条边，该边的两个结点必然属于不同的两个子树。分别以两个结点i,j为起点，对子树i进行深度优先搜索（可以保证不会搜到另一棵子树上，否则出现回路；但是需要传入j，判断第一步不能走到j），计算出子树i的结点个数。对于子树j同理。最后得到删除该边的代价，并与maxm比较。

具体代码如下：

class Solution {
public:
    vector<pair<int,int>> path[100001];
    int count = 1;
    int dfs(int start, int pre, int neighbour)
    {
        for (int i=0;i<path[start].size();i++)
        {
            //判断下一步去的结点不能是上一步来的结点，也不能是另一个树的结点
            if (path[start][i].first != pre && path[start][i].first!=neighbour)
            {
                //遍历到一个新结点，计数器就加一
                count++;
                dfs(path[start][i].first, start, neighbour);
            }
        }
        return count;
    }

    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        int maxm = 0;
        for (int i=0;i<n-1;i++)
        {
            path[u[i]].push_back({v[i],w[i]});
            path[v[i]].push_back({u[i],w[i]});
        }
        for (int i=0;i<n-1;i++)
        {
            //每次dfs之前，count要初始化
            count = 1;
            int count1 = dfs(u[i],-1,v[i]);
            count = 1;
            int count2 = dfs(v[i],-1,u[i]);
            maxm = max(maxm, count1*count2*w[i]);
        }
        return maxm;
    }
};

时间复杂度：。对于每一条边，都对所有结点进行了一次遍历。
空间复杂度：。创建了一个邻接矩阵来记录边和结点的信息。

方法二

方法一中对于每一个不同的子树都需要通过dfs遍历，来计算结点个数，消耗的代价过大，可以进行优化。

当我们以某个结点为根的时候，可以把图转换为一棵树，于是对于每条边，我们把树分为父结点所在的树a和子节点为根的树b。以某个结点为根的子树的结点总数，等于其每个子树的结点数求和，再加1。所以我们可以通过dfs求出b的结点总数，而子树a的结点总数为n-|b|。

这样，我们可以通过dfs，在遍历到一个点的时候，以其为根的子树的结点总数是已知的了，可以计算出对应边（该点与其父结点之间的边）的破坏代价，从而降低了时间复杂度。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 城市个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @param w int整型vector 
     * @return long长整型
     */
    vector<pair<int,int>> path[100001];
    int count[100001];
    long long maxm = 0;
    void dfs(int start, int pre, int n)
    {
        //初始化，该结点所在的子树中必包含自身
        count[start] = 1;
        for (int i=0;i<path[start].size();i++)
        {
            //判断下一步去的结点不能是上一步来的结点
            if (path[start][i].first != pre)
            {
                int next = path[start][i].first;
                dfs(next, start, n);
                long long t = count[next]*(n - count[next])*path[start][i].second;
                maxm = max(maxm,t);
                //将已经求得的该结点的子树的结点数加上去
                count[start] += count[next];
            }
        }
    }

    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        for (int i=0;i<n-1;i++)
        {
            path[u[i]].push_back({v[i],w[i]});
            path[v[i]].push_back({u[i],w[i]});
        }
        dfs(1,0,n);
        return maxm;
    }
};

时间复杂度：。在遍历点的同时，判断了每条边的破坏代价，只遍历了一次。
空间复杂度：。创建了一个邻接矩阵来记录边和结点的信息。