蓝桥杯之生命之数（dp dfs 邻接矩阵）

#include<iostream>  
using namespace std;  

int mx = 0;    //最大子树的权值  

void dfs(int **mat,int V_num,int V,bool *vis,int *W)          
//参数1：邻接矩阵 参数2：节点数 参数3：根节点 参数4：访问数组 参数5：节点权值  
{  
    vis[V] = false; //根节点被访问  
    for (int i = 1; i <= V_num; i++)     //遍历所有节点  
    {  
        if (vis[i] && mat[V][i])        //如果节点未被访问 并且与节点i之间存在边  
        {  
            dfs(mat, V_num, i, vis, W);     //递归子节点i  
            if (W[i] + W[V] > W[V])      //如果子节点i +根节点V的权值大于根节点V  
                W[V] = W[i] + W[V];         //那么根节点V的权值变为 子节点i+根节点V  
            if (W[V] > mx)  
                mx = W[V];     //记录最大子树  
        }  
    }  
}  

int main()  
{  
    int n;      //节点数  
    cin >> n;  
    int *weight = new int[n+1]; //节点权值  
    for (int i = 1; i <= n; i++)       
        cin >> weight[i];  
    int **mat = new int*[n+1];  //构造邻接矩阵  
    for (int i = 0; i <= n; i++)  
        mat[i] = new int[n + 1];  
    bool *vis = new bool[n + 1];        //构造访问数组  
    for (int i = 0; i <= n; i++)     //邻接矩阵、访问数组初始化  
    {  
        for (int j = 0; j <= n; j++)  
            mat[i][j] = 0;  
            vis[i] = true;  
    }  

    int s, e;  
    for (int i = 0; i < n - 1; i++)  //如果顶点间存在边则为 1 否则为0  
    {  
        cin >> s >> e;  
        mat[s][e] = mat[e][s] = 1;  
    }  
    dfs(mat, n, 1, vis, weight);  
    cout << mx << endl;        //输出最大子树权值  
    return 0;  
}