Pat class a a1053 path of equal weight (tree traversal)

Given a non-empty tree with root R, and with weight Wi​ assigned to each tree node Ti​. 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<230, the given weight number. The next line contains N positive numbers where Wi​ (<1000) corresponds to the tree node Ti​. 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 {A1​,A2​,⋯,An​} is said to be greater than sequence {B1​,B2​,⋯,Bm​} if there exists 1≤k<min{n,m} such that Ai​=Bi​ for i=1,⋯,k, and Ak+1​>Bk+1​.

Sample Input:

20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19

Sample Output:

10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2

The question ： Give the weight of all nodes and a fixed value s, And the sub node number of each node with sub nodes , Find the sum of the tree path weights equal to the given fixed value s The weight of each node of .

Ideas ： Method 1 , Sort the child nodes of each node from large to small , Then proceed DFS Traverse , Traversal boundary is sum==s, And The node traversed is a leaf node , Put such a path into path Array , After traversing this path, output , Until all paths are traversed .

        Method 2 ,DFS Traverse all paths , The satisfied path is put into ans Inside , Last in sort In the function , use greater The comparison function implements sorting from small to large in dictionary order , Output after sorting ans All paths inside .

The last test point can't pass , as a result of 1053 Path of Equal Weight (30 branch )（ Pass the last test point ）_ Yongye and other Tianming blogs -CSDN Blog

Method one code ：

	 #include<iostream>
	#include<vector>
	#include<algorithm>
	using namespace std;
	const int maxn=110;
	int n,m,k,child,s,id;
	int path[maxn];
	
	struct node{
		int weight;
		vector<int > child;// The address of the child node ; 
	}Node[maxn];
	
	bool cmp(int a,int b){// Is to arrange integer arrays , Not an array of structures , Don't write Node a,Node b; 
		return Node[a].weight>Node[b].weight;
	}
	void DFS(int index,int nodenum,int sum){
		if(sum>s)return ;// Recursive boundary ;
		if(sum==s){
			if(Node[index].child.size()!=0)return ;// It's not a leaf node , With child nodes ,sum==s It is also not satisfied with the meaning of the topic ;
			for(int i=0;i<nodenum;i++){
				printf("%d",Node[path[i]].weight);//path The address of the node of the path is recorded （ Subscript ）, Instead of the weight of the node ; 
				i==nodenum-1?printf("\n"):printf(" ");
			} 
		}
		for(int i=0;i<Node[index].child.size();i++){// Traverse the child nodes under this node ;
			int child=Node[index].child[i]; 
			path[nodenum]=Node[index].child[i];// use nodenum Subscript , If the path is illegal, it can be overwritten and placed in advance when returning to the previous layer path Illegal node of ; 
			DFS(child,nodenum+1,sum+Node[child].weight);// Recursive , Recurse the child nodes under this node ; 
		}
	}
	int main( ){
		scanf("%d%d%d",&n,&m,&s);
		for(int i=0;i<n;i++)scanf("%d",&Node[i].weight);// Input the weights of nodes in turn ; 
		for(int i=0;i<m;i++){//m A node has child nodes ; 
			scanf("%d %d",&id,&k);// The number of this node , The number of its child nodes ;
			for(int j=0;j<k;j++){
				scanf("%d",&child);
				Node[id].child.push_back(child);
			}
			// Child node sorting ; 
			sort(Node[id].child.begin(),Node[id].child.end( ),cmp);// Because it needs to be output in increasing order , Then it's important to traverse first and put it in first path, This effect can be achieved ; 
		}
		path[0]=0;//0 Node number is the root node , Starting from the root node , Initialize first path[0]=0; 
		DFS(0,1,Node[0].weight);// Start with the first node , therefore nodenum The initial value of 1, initial sum It should be the weight of the first node, not 0; 
		return 0;
	} 

Method 2 ac Code ：
 

	 #include<iostream>
	#include<vector>
	#include<algorithm>
	using namespace std;
	const int maxn=110;
	int n,m,k,child,s,id;
	vector<int> path;// Store the path nodes that meet the meaning of the question ; 
	vector<vector<int>> ans;// Two dimensional array , Store the weights of each node of all paths that meet the conditions ; 
	struct node{
		int weight;
		vector<int > child;// The address of the child node ; 
	}Node[maxn];
	

	void DFS(int index,int nodenum,int sum){
		if(sum>s)return ;// Recursive boundary ;
		if(sum==s){
			if(Node[index].child.size()!=0)return ;// It's not a leaf node , With child nodes ,sum==s It is also not satisfied with the meaning of the topic ;
			ans.push_back(path);// Put this path into ans Inside ;
			return ; 
		}
		for(int i=0;i<Node[index].child.size();i++){// Traverse the child nodes under this node ;
			int child=Node[index].child[i]; 
			path.push_back(Node[child].weight); 
			DFS(child,nodenum+1,sum+Node[child].weight);// Recursive , Recurse the child nodes under this node ;
			path.pop_back( );//vector It's using pop_back Clear the tail element , Prepare for the next child node ; 
		}
	}
	int main( ){
		scanf("%d%d%d",&n,&m,&s);
		for(int i=0;i<n;i++)scanf("%d",&Node[i].weight);// Input the weights of nodes in turn ; 
		for(int i=0;i<m;i++){//m A node has child nodes ; 
			scanf("%d %d",&id,&k);// The number of this node , The number of its child nodes ;
			for(int j=0;j<k;j++){
				scanf("%d",&child);
				Node[id].child.push_back(child);
			}
		}	
		path.push_back(Node[0].weight);
		DFS(0,1,Node[0].weight);// Start with the first node , therefore nodenum The initial value of 1, initial sum It should be the weight of the first node, not 0; 
		sort(ans.begin(),ans.end(),greater<vector<int>>( ));// Sort in descending dictionary order ; 
		for(int i=0;i<ans.size();i++){
			for(int j=0;j<ans[i].size();j++){
				printf("%d",ans[i][j]);
				j==ans[i].size()-1?printf("\n"):printf(" ");
			}
		} 
		return 0;
	} 

Instead, use greater function , Sort by dictionary order from big to small , Avoid the situation that the nodes of the same layer have the same weight without sorting .