一般树的遍历

源自广东外语外贸大学第16届(2019)程序设计校赛 B 葱葱树

Description

 输入一棵大小为n有根树，节点编号为1到n且以编号为1的节点为根。这棵树的结点有0~9的权值。接下来给出Q个查询 每个查询输入一个结点的编号，输出以该节点为根的子树的叶子结点的权值数量。

Input

一个 N代表这棵树的结点的数量 N( N <= 10^5 ) 接下来N-1行输入，每行输入u,v代表v是u的直接子节点, 结点编号从1开始（1 <= u,v <= N） 接下来输入一行，N个数字,代表每个结点的权值 接下来一行,有一个数字Q (Q <= 10 ^ 4) 接下来一行，有Q个数字，每个数字代表查询的结点编号

Output

输出Q行，每行9个数字，代表以该查询的节点为根的子树的叶子结点的0~9的权值的数量

AC代码： 

#includeusing namespace std;struct tree{vectorto;//存结点孩子int val;//存改结点的权值}a[100000];void dfs(int x,int cn[]){if(a[x].to.empty())//如果是叶子结点{cn[a[x].val]++;return;}for(auto v:a[x].to){dfs(v,cn);}}int main(){int n;cin>>n;for(int i=1;i>u>>v;a[u].to.push_back(v);}for(int i=1;i>a[i].val;int q;cin>>q;while(q--){int x;cin>>x;int cn[10]={0};dfs(x,cn);for(int i=0;i<10;i++){if(i) cout<<" ";cout<<cn[i];}cout<<endl;}return 0;}