题意：
            有一棵节点为 n 的树，树的每条边都有一个权值 w 。
          每条边都有一个重要程度：等于这条边所分隔的两个集合的数量之积，再乘上这条边的权重。
            问树的哪条边计算的值最大，输出这个最大值。

 方法一：
dfs


思路：用邻接表建树。
        dfs后序遍历，枚举每条边计算的值，用 res 维护最大值。 
        
        关键点：去掉一条边后，一棵树就一分为二，变成两个连通块（即两个集合）
                        计算两个集合的数量之积即是求解的城市的对数，
                        最后再乘上这条边的权重即可。
                       并用 res 维护最大值。
 




#define ll long long 

class Solution {
public:
    ll res=0;
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        vector<vector<pair<int,int>>> g(n+1);
        for(int i=0;i<n-1;i++){//建树
            g[u[i]].push_back({v[i],w[i]});
            g[v[i]].push_back({u[i],w[i]});
        }
        dfs(1,1,g,n);//从任意节点开始都行
        return res;
    }
    int dfs(int x,int fa,vector<vector<pair<int,int>>> g,int n){
        int sum=0;//记录以节点x为根节点的子树中节点数量
        int num=g[x].size();
        for(int i=0;i<num;i++){//遍历节点x的每条边
            int y=g[x][i].first,z=g[x][i].second;
            if(y!=fa){//如果未访问
                int m=dfs(y,x,g,n);//得到节点x的各子树中的节点数量
                sum+=m;
                res=max(res,(ll)m*(n-m)*z);//维护最大值
            }
        }
        return sum+1;
    }
};

时间复杂度：
空间复杂度：

方法二：
链式前向星存储


思路：
        同方法一的思路一致，方法一用邻接表存储，方法二用链式前向星存储边集。
        
        优化了空间存储，使得空间复杂度从

#define ll long long 

class Solution {
public:
    ll res=0;
    int e[200005],val[200005],ne[200005],h[100005];
    int idx=0;
    void add(int x,int y,int z){//添加边
        e[idx]=y;
        val[idx]=z;
        ne[idx]=h[x];
        h[x]=idx++;
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w){
        memset(h,-1,sizeof(h));
        for(int i=0;i<n-1;i++){
            add(u[i],v[i],w[i]);//无向图
            add(v[i],u[i],w[i]);
        }
        dfs(1,1,n);
        return res;
    }
    int dfs(int x,int fa,int n){
        int sum=0;//记录以节点x为根节点的子树数量
        
        for(int i=h[x];i!=-1;i=ne[i]){//遍历节点x的每条边
            int y=e[i],z=val[i];
            if(y!=fa){//如果未访问
                int m=dfs(y,x,n);//得到节点x的各子树中的节点数量
                sum+=m;
                res=max(res,(ll)m*(n-m)*z);//维护最大值
            }
        }
        return sum+1;
    }
    
};


时间复杂度：
空间复杂度：