# 题目

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, the number of nodes in a tree,$M(, the number of non-leaf nodes, and$0, 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:

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 $\left\{A_{1}, A_{2}, \cdots, A_{n}\right\}$ is said to be greater than sequence $\left\{B_{1}, B_{2}, \cdots, B_{m}\right\}$ if there exists $1 \leq k<\min \{n, m\}$ such that $A_{i}=B_{i}$ for $i=1, \cdots, k,$ and $A_{k+1}>B_{k+1}$.

# 题解

## 思路

• 题目给的是一个节点有权重的无环图
• 让你从根部找到符合相应权重的路径们
• 注意，路径的起点是根部没有疑问，但是终点必须是叶子节点。这个可以从范例中看出来。
• 那么很显然地就是DFS了。还不用记录有无访问过，比较简单的DFS
• 但是对那些排序需要依靠一些小窍门
• 题目的排序要求是，如果两个路径的第i个节点上相同，那么判断第i+1个节点，哪个小就是哪个路径小。
• 一般来说我们容易写成lambda x:(x,x,x,...)这样的形式，可是问题是这些路径的长度是不确定的，而且不是所有路径的长度是一样的。
• 我这里使用了一些奇巧淫技。
• 注意这里的排序和字符串排序很像。
• 那我们就可以把它映射成字符串的样子排序。
• 注意不是直接用str() 这样映射，这样的话10反而比9小。
• 要使用chr()这样排序，直接映射到ASCII码。
• 这样就不需要单独列出来一个排序函数了。
• 想到这点不容易（我夸我自己）

## 数据结构

• weight 是一个列表，代表各个节点的权重
• 下标是ID
• 值是这个节点的权重
• sons 是一个列表，代表各个节点的孩子节点
• 下标是ID
• 值是一个列表，包含这个ID的所有孩子
• 如果没孩子则值为空
• temp_weight 记录深搜过程中的临时权重和
• path 记录神搜过程中的临时路径
• ans记录答案，是一个列表，包含了所有符合要求的路径。
• 一条路径是一个列表

## 算法

• 如思路所说，深度优先遍历然后按照chr()组成的字符串排序。

## 代码

• 因为使用Python能够AC，因此只放了Python的代码。