C++ 深度优先搜索算法求解树节点权值和

#include #include #include #include using namespace std;

const int maxm = 100005; vector child[maxm]; // 存储每个节点的子节点 double val[maxm],z,r,sum; // val存储每个叶子节点的值，z为初始值，r为衰减率，sum为最终结果

// 深度优先搜索函数 void dfs(int id,double w){ if(val[id]){ // 如果当前节点是叶子节点，将叶子节点的值乘以权重w加到sum中 sum = sum+wval[id]; }else{ // 如果当前节点不是叶子节点，递归调用dfs函数 for(int i=0;i<child[id].size();i++){ dfs(child[id][i],wr); }
}

int main() { int n,m,k; memset(val,0,sizeof(val)); // 将val数组初始化为0 sum = 0; // 将sum初始化为0 scanf('%d %lf %lf',&n,&z,&r); // 输入n，z和r r = (100-r)/100; // 将r转换为衰减率 for(int i=0;i<n;i++){ // 输入每个节点的信息 scanf('%d',&m); if(!m){ // 如果节点是叶子节点，直接输入叶子节点的值 scanf('%lf',&val[i]); }else{ // 如果节点不是叶子节点，输入子节点的编号 for(int j=0;j<m;j++){ scanf('%d',&k); child[i].push_back(k); }
} } dfs(0,z); // 调用dfs函数计算最终结果 printf('%d\n',(int)sum); // 输出最终结果 return 0; }