题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805424153280512

这题说不复杂也有点复杂，说复杂也不是很复杂
注意点

  1. 0结点是树根
  2. 孩子结点使用vector数组存储节省空间
  3. 使用sort根据权值对孩子结点进行排序，这样就可以使权值大的先遍历到，使输出符合权值递减
  4. 最精髓的是第33行代码，一开始我用的是push_back，导致错误，这题应该直接覆盖对应数组单位
  5. 记一下DFS的格式
  1. void DFS(int root, int path_num, int sum){

代码

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  6. const int maxn = 110;
  7. int n, m, s;//n是结点总数，m是非叶子结点数量，s是待求的权值和
  8. int weight[maxn];
  9. vector<int> path(maxn);
  11. struct Node{
  12.     int data, weight;
  13.     vector<int> child;
  14. }node[maxn];
  16. bool cmp(int a, int b){
  17.     return node[a].weight > node[b].weight;
  18. }
  20. void DFS(int root, int path_num, int sum){
  21.     if(sum > s) return;
  22.     if(sum == s){//这个时候说明到达了叶子结点
  23.         if(sum == s && node[root].child.size() != 0) return;
  24.         for(int i = 0; i < path_num; i++){
  25.             printf("%d",node[path[i]].weight);
  26.             if(i != path_num - 1) printf(" ");
  27.         }
  28.         printf("\n");
  29.         return;
  30.     }
  31.     for(int i = 0; i < node[root].child.size(); i++){
  32.         int child = node[root].child[i];
  33.         path[path_num] = child;
  34.         DFS(child, path_num + 1, sum + node[child].weight);
  35.     }
  36. }
  38. int main(){
  39.     scanf("%d%d%d", &n, &m, &s);
  40.     for(int i = 0; i < n; i++) scanf("%d", &node[i].weight);
  41.     int tempi, leafnum,temp;
  42.     for(int i = 0; i < m; i++){
  43.         scanf("%d%d",&tempi, &leafnum);
  44.         for(int j = 0; j < leafnum; j++){
  45.             scanf("%d",&temp);
  46.             node[tempi].child.push_back(temp);
  47.         }
  48.         sort(node[tempi].child.begin(), node[tempi].child.end(), cmp);
  49.     }
  50.     path.push_back(0);
  51.     DFS(0, 1, node[0].weight);
  52.     return 0;
  53. }