关键词：
1053. Path of Equal Weight (30)
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 Figure 1: 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 Figure 1.
Figure 1
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 < minn, 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
题目大意：给出树的结构和权值，找从根结点到叶子结点的路径上的权值相加之和等于给定目标数的路径，并且从大到小输出路径
分析：对于接收孩子结点的数据时，每次完全接收完就对孩子结点按照权值进行排序（序号变，根据权值变），这样保证深度优先遍历的时候直接输出就能输出从大到小的顺序。
#include <bits/stdc++.h>
using namespace std;
struct NODE
int value,id;
vector<NODE>son;
;
vector<NODE> v;
int s;
int path[1000];
void dfs(int id, int w, int cnt)
if(w == s && v[id].son.size() ==0)
printf("%d", v[path[0]].value);
for(int i=1; i<cnt; i++)
printf(" %d", v[path[i]].value);
printf("\n");
return;
for(int i=0; i<v[id].son.size(); i++)
if( w + v[id].son[i].value <= s)
path[cnt] = v[id].son[i].id;
dfs(v[id].son[i].id, w+v[id].son[i].value, cnt+1);
bool cmp(NODE a, NODE b)
return a.value > b.value;
int main()
int n, m;
scanf("%d%d%d", &n, &m,&s);
v.resize(n);
for(int i=0; i<n; i++)
scanf("%d", &v[i].value);
v[i].id = i;
for(int i = 0; i<m; i++)
int id, num;
scanf("%d%d", &id, &num);
int value;
for(int j = 0; j<num; j++)
scanf("%d", &value);
v[id].son.push_back(v[value]);
sort(v[id].son.begin(), v[id].son.end(), cmp);
path[0] = 0;
dfs(0,v[0].value,1);
pat1053.pathofequalweight(30)
1053.PathofEqualWeight(30)时间限制100ms内存限制65536kB代码长度限制16000B判题程序Standard作者CHEN,YueGivenanon-emptytreewithrootR,andwithweightWi assignedtoeachtreenodeTi.The weightofapathfromRtoLisdefinedtobeth 查看详情
pat1053pathofequalweight（30分）(代码片段)
1053 PathofEqualWeight（30 分）Givenanon-emptytreewithroot R,andwithweight W?i?? assignedtoeachtreenode T?i??.The weightofapathfrom R to L isdefined 查看详情
patadvancedlevel1053pathofequalweight(代码片段)
1053PathofEqualWeight(30)（30分）Givenanon-emptytreewithrootR,andwithweightW~i~assignedtoeachtreenodeT~i~.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnod 查看详情
1053pathofequalweight(30分)难度:一般/树的遍历(代码片段)
https://pintia.cn/problem-sets/994805342720868352/problems/994805424153280512#include<bits/stdc++.h>usingnamespacestd;constintN=1e3+10;vector<int>ve[N];vector<vector< 查看详情
patadvanced1053pathofequalweight(30)[树的遍历](代码片段)
题目Givenanon-emptytreewithrootR,andwithweightWiassignedtoeachtreenodeTi.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnodeL.Nowgivenanyweightedtree,youaresupposedtofindallthepathswiththeirweightsequaltoagivennumber.Forexample,let’sconsiderthetrees... 查看详情
1053pathofequalweight(30分)(并查集)(代码片段)
Givenanon-emptytreewithroot R,andwithweight W?i?? assignedtoeachtreenode T?i??.The weightofapathfrom R to L isdefinedtobethesumoftheweightsofallthenodesalongthepathfrom R toanyleafnode L.Nowgivenanyweightedtree,youaresupposedtofindallthepat... 查看详情
pat甲题题解-1053.pathofequalweight(30)-dfs
由于最后输出的路径排序是降序输出，相当于dfs的时候应该先遍历w最大的子节点。链式前向星的遍历是从最后add的子节点开始，最后添加的应该是w最大的子节点，因此建树的时候先对child按w从小到大排序，然后再add建边。水题... 查看详情
pat1053.pathofequalweight
Givenanon-emptytreewithrootR,andwithweightWiassignedtoeachtreenodeTi.TheweightofapathfromRtoLisdefinedtobethesumoftheweightsofallthenodesalongthepathfromRtoanyleafnodeL.Nowgivenanyweightedtree,youares 查看详情
树的遍历——a1053.pathofequalweight(30)只可dfs不可bfs(代码片段)
#include<bits/stdc++.h>#include<stdio.h>#include<stdlib.h>#include<queue>usingnamespacestd;constintMAXN=110;structNodeintweight;vector<int>child;Node[MAXN];boolcmp(inta,intb)returnNode[a].weight>Node[b].weight;intn,m,S;//结点数，边数及给定的和i... 查看详情
1053pathofequalweight（30分）（树的遍历）(代码片段)
题目大意：给出树的结构和权值，找从根结点到叶子结点的路径上的权值相加之和等于给定目标数的路径，并且从大到小输出路径#include<bits/stdc++.h>usingnamespacestd;intn,m,sum;constintN=120;structnodeintw;vector<int>p;tree[N];boolcmp(inta,in... 查看详情
pat1053pathofequalweight(代码片段)
Givenanon-emptytreewithroot R,andwithweight W?i?? assignedtoeachtreenode T?i??.The weightofapathfrom R to L isdefinedtobethesumoftheweightsofallthenodesalongthepathfrom Rtoanyleafnode L.Nowgivenanyweightedtree,youaresupposedtofindallthepathswith... 查看详情
[pat]a1053pathofequalweight(代码片段)
(要熟练！)（树的遍历）题目大意(题目链接)https://pintia.cn/problem-sets/994805342720868352/problems/994805424153280512题目大意：给出树的结构和权值，找从根结点到叶子结点的路径上的权值相加之和等于给定目标数的路径，并且从大到小输出... 查看详情
1053pathofequalweight(代码片段)
1.这道题考察的是树(注意不是二叉树，子结点个数不限，没有顺序)的先根遍历，即DFS，因为BFS做不到把祖先节点的值累计到当前结点。我这里使用了一个copyDadWeis函数实现，把父节点的权重向量拷贝给子节点&#... 查看详情
pat甲级目录
树备注1004 CountingLeaves 1020TreeTraversals 1043IsItaBinarySearchTree 判断BST，BST的性质1053PathofEqualWeight 1064CompleteBinarySearchTree 完全二叉树的顺序存储，BST的性质1066RootofAVLTre 查看详情
10.22-10.28博客精彩回顾
...4.构建FTP文件传输服务器5.*PAT_甲级_1053PathofEqualWeight(30分)(C++)【数组排序/DFS】6.LSISAS2208阵列卡刷IT模式7.【原子样式实践】第10篇原子样式到原子设计 查看详情
1004countingleaves(30)（30分）(代码片段)
1004CountingLeaves(30)（30分）Afamilyhierarchyisusuallypresentedbyapedigreetree.Yourjobistocountthosefamilymemberswhohavenochild.InputEachinputfilecontainsonetestcase.Eachcasestartswithalinecontaining0&l 查看详情
如何写表达式 a<=20?b=30:c=30;这样 30 只使用一次？
】如何写表达式a<=20?b=30:c=30;这样30只使用一次？【英文标题】：Howtowritetheexpressiona<=20?b=30:c=30;suchthat30isusedonlyonce?【发布时间】：2021-01-3114:44:25【问题描述】：我正在关注一本关于c编程的书，遇到了这个例子：a<=20?b=30:c=30;... 查看详情
如何使用numpy数组的引用坐标处理奇怪的索引行为？(代码片段)
...。请参阅下面的示例：t=np.zeros((5,5))coord=[[2,3],[1,2]]t[coord]=30print(t)输出：[[0.0.0.0.0.][0.0.0.0.0.][0.30.0.0.0.][0.0.30.0.0.][0.0.0.0.0.]]但是如果列表只有一点：t=np.zeros((5,5))coord=[[2,3]]t[coord]=30print(t)输出：[[0.0.0.0.0.][0.0.0.0.0.][30.30.30.30.30.][30.30.30... 查看详情