给定一个非空树，树中每个结点都有一个权重。路径的权重定义为沿着从根结点到任意叶结点的路径上所有结点的权重之和。你需要找到权重等于给定数字的所有路径。
输入第一行先给出 3 个正整数 N、M、S，分别表示树中的结点数，树中非叶子结点数和路径权重。第二行给出 N 个正整数，第 i 个数表示结点 i 的权重。接下来 M 行，每行按ID K ID[1] ID[2] ... ID[K]的格式给出结点 ID 的 K 个子结点。
以字典序非递增顺序打印所有权重为 S 的路径，注意打印的不是结点编号，而是结点的权重。每个路径占据一行，所有数字必须用空格分隔，行尾不得有多余的空格。
我们使用一个数组 tree 存储所有的结点，通过深度优先遍历来解决本题。由于需要按字典序非递增的顺序打印路径，我们在读取完结点的所有子结点后，可以将这些子结点按权重从大到小排序，这样可以保证在进行深度优先遍历时，字典序非递增顺序靠前的路径会先被遍历到。 额外定义一个 vector 类型的全局变量 path 存储路径。由根结点发起深度优先遍历，记录下当前路径的权重之和，如果遍历到的当前结点是叶子结点且路径权重之和等于 S，将当前路径输出即可。
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 105;
gg ni, mi, si;
vector<gg> w(MAX), path;
vector<vector<gg>> tree(MAX);
void dfs(gg v, gg s) { // v表示当前结点，s表示当前路径权重值和
s += w[v];
if (s > si or (s == si and not tree[v].empty())) {
return;
}
if (s == si and tree[v].empty()) {
for (gg i = 0; i < path.size(); ++i) {
cout << path[i] << " ";
}
cout << w[v] << "\n";
return;
}
path.push_back(w[v]);
for (gg i : tree[v]) {
dfs(i, s);
}
path.pop_back();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> ni >> mi >> si;
for (gg i = 0; i < ni; ++i) {
cin >> w[i];
}
for (gg i = 0; i < mi; ++i) {
gg id, ki, ai;
cin >> id >> ki;
while (ki--) {
cin >> ai;
tree[id].push_back(ai);
}
sort(tree[id].begin(), tree[id].end(),
[](gg a, gg b) { return w[a] > w[b]; });
}
dfs(0, 0);
return 0;
}