1053 Path of Equal Weight（30 分）

1053 Path of Equal Weight（30 分）
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

include

include

include

include

using namespace std;
const int maxn=1e4+10;
struct Node{
int weight;
vectorchild;
}node[maxn];
int n,m,s,path[maxn];

bool cmp(int a,int b){
return node[a].weight >node[b].weight ;
}

void dfs(int index,int numnode,int sum){
if(sum>s) return ;
if(sum==s){
if(node[index].child.size() !=0)
return;
else{
for(int i=0;i