Given a non-empty tree with root R, and with weight W?i?? assigned to each tree node T?i??. The weight of a path from R to L is defined to be the sum of the weights of all the nodes along the path from R to any leaf node L.
Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let's consider the tree showed in the following figure: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in the figure.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 0<N≤100, the number of nodes in a tree, M (<N), the number of non-leaf nodes, and 0<S<2?30??, the given weight number. The next line contains N positive numbers where W?i?? (<1000) corresponds to the tree node T?i??. Then M lines follow, each in the format:
ID K ID[1] ID[2] ... ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID's of its children. For the sake of simplicity, let us fix the root ID to be 00.
Output Specification:
For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.
Note: sequence {A?1??,A?2??,?,A?n??} is said to be greater than sequence {B?1??,B?2??,?,B?m??} if there exists 1≤k<min{n,m} such that A?i??=B?i?? for i=1,?,k, and A?k+1??>B?k+1??.
解答：
该题可以直接用dfs求解，在找到符合条件的叶节点时，便将它保存下来。
那么如何求其路径呢，那么我们可以用一个数组来保存一个节点的父节点， 即tree[i] = j; 那么节点 i 的父节点就是 j 。然后通过递归来求路径，思路比较清晰；
那么如何对路径进行排序呢？这时我们可以在保存路径时，对一个根的子树按权值排序，这样，我们用dfs遍历时，便会先访问权值高的节点，这样就不需要另外排序啦。
---------------------------------------------------------------------------------------------
今天，我在博客 1053. Path of Equal Weight (30)-PAT甲级真题(树的遍历)中找到了一个输出路径的更简洁的方法，时间效率其实大致相同。就是每次遍历时，都保存下当前的节点，并记录当前是第几个节点，这样便可以愉快地输出路径了。代码见下。
学无止境，加油！
AC代码如下：
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>#define maxn 105using namespace std;int n, m, s;
vector<int> weights;
int tree[maxn]; //保存第i个节点的父亲
vector<int> e[maxn];
vector<int> paths; //记录符合条件的叶节点 void dfs(int v, int w)
{if(e[v].size() == 0 && w == s){paths.push_back(v);} for(int i = 0; i < e[v].size(); ++i){int node = e[v][i];dfs(node, w + weights[node]);}
}void print(int v)
{if(v == 0){printf("%d", weights[v]);return; } print(tree[v]);printf(" %d", weights[v]);
}bool cmp(int v1, int v2)
{return weights[v1] > weights[v2];
}int main()
{scanf("%d %d %d", &n, &m, &s);for(int i = 0; i < n; ++i){int weight;scanf("%d", &weight);weights.push_back(weight);}for(int i = 0; i < m; ++i){int v, nc;scanf("%d %d", &v, &nc);for(int j = 1; j <= nc; ++j){int child;scanf("%d", &child);e[v].push_back(child);tree[child] = v;}//对边按权值从大到小排序，这样可以保证输出有序 sort(e[v].begin(), e[v].end(), cmp);}dfs(00, weights[0]);for(int i = 0; i < paths.size(); ++i){print(paths[i]);printf("\n");}return 0;
}#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>#define maxn 105using namespace std;int n, m, s;
vector<int> weights;
int tree[maxn]; //保存第i个节点的父亲
vector<int> e[maxn];
vector<int> path(maxn); //记录符合条件的叶节点 void dfs(int v, int num, int w)
{if(e[v].size() == 0 && w == s){for(int i = 0; i < num; ++i){printf("%d%c", weights[path[i]], i != num-1 ? ' ' : '\n');}return;} for(int i = 0; i < e[v].size(); ++i){int node = e[v][i];path[num] = node; dfs(node, num+1, w + weights[node]);}
}bool cmp(int v1, int v2)
{return weights[v1] > weights[v2];
}int main()
{scanf("%d %d %d", &n, &m, &s);for(int i = 0; i < n; ++i){int weight;scanf("%d", &weight);weights.push_back(weight);}for(int i = 0; i < m; ++i){int v, nc;scanf("%d %d", &v, &nc);for(int j = 1; j <= nc; ++j){int child;scanf("%d", &child);e[v].push_back(child);tree[child] = v;}//对边按权值从大到小排序，这样可以保证输出有序 sort(e[v].begin(), e[v].end(), cmp);}path[0] = 0;dfs(00, 1, weights[0]);return 0;
}