Main idea of the title:

Given a tree and the weight of each node, find the path from all root nodes to leaf nodes, so that the sum of the weight on each path is equal to the given constant S. if there are multiple paths, output according to the non increasing sequence of paths

Algorithm idea:

Considering the traversal of the tree, since it is necessary to find the path from all root nodes to leaf nodes, it is natural to think of traversing the tree in sequence, and use $path $to save the current search path and $result $to save all qualified paths. If the current node is a leaf node, add this node to $path $first, and then calculate the total weight of all nodes in $path $if it is equal to the given S, Then add $path $to $result $. Then you have to go back. First exit the leaf node from $path $, and then return. If the current node is not a leaf node, first add the current node to $path $, then recursively traverse each child node, and then exit the current node from $path $. In this way, the search process of the whole tree is completed. After the search, $result $saves all the paths that meet the conditions, then sorts each path sequence of $result $from large to small in dictionary order, and finally outputs it.

Note:

• 1. Without sorting, you can get 10 points and test points 0 and 2 are wrong.
• 2. Both the error of test point 2 and the segment error of test point 5 are due to the problem of sorting function. First of all, we should pay attention to the sorting of weights, not the ID of nodes (this is easy to be mistaken), and then we should write the positive and negative comparison logic of the two sequences, that is, the return values of the same position I, a [i] > b [i] and a [i] < B [i], and we should also deal with all exactly the same sequences, Otherwise, a segment error occurs in test point 5. To sum up, the sorting function has to deal with all possible situations.

Submit results:

AC Code:

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct Node{
    int weight;
    vector<int> child;
}node[110];

vector<int> path;//Current search path
vector<vector<int> > result;//All solutions satisfying conditions

bool cmp(vector<int> a,vector<int> b){
    int len = min(a.size(),b.size());
    for(int i=0;i<len;++i){
        if(node[a[i]].weight>node[b[i]].weight){
            return true;
        }else if(node[a[i]].weight<node[b[i]].weight){//If this is not written, there will be a test point 2 error 
            return false;
        }
    }
    return a.size()>b.size();// There is an error in not writing this paragraph 
}

void preTraverse(int root,int weight){
    if(node[root].child.empty()){
        // leaf node 
        path.push_back(root);
        // Calculate the weight of the current path
        int sum = 0;
        for(int i=0;i<path.size();++i){
            sum += node[path[i]].weight;
        }
        if(sum==weight){
            result.push_back(path);
        }
        //Back off
        path.pop_back(); 
        return ;
    }
    //Select current node 
    path.push_back(root);
    for(int i=0;i<node[root].child.size();++i){
        preTraverse(node[root].child[i],weight);
    }
    path.pop_back();
}


int main(){
    int N,M,S;//Total number of nodes, total number of non leaf nodes, weight to be queried
    scanf("%d %d %d",&N,&M,&S);
    for(int i=0;i<N;++i){
        scanf("%d",&node[i].weight);
    } 
    int ID,K;
    for(int i=0;i<M;++i){
        scanf("%d %d",&ID,&K);
        int child;
        for(int j=0;j<K;++j){
            scanf("%d",&child);
            node[ID].child.push_back(child);
        }
    }
    preTraverse(0,S);
    // Output the sequence of result s in reverse order according to the dictionary order
    sort(result.begin(),result.end(),cmp);
    for(int i=0;i<result.size();++i){
        for(int j=0;j<result[i].size();++j){
            printf("%d",node[result[i][j]].weight);
            if(j<result[i].size()-1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}