PTA甲级—树

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <cmath>
#define ll long long
#define inf 0x3f3f3f
#define pii pair<int, int>
using namespace std;
const int maxn = 1e4+100;
int n, m, k, par, child;
int cnt, head[maxn];
int level, ans[maxn];
struct node{
    int to, nxt;
}e[maxn];

void add(int u, int v){
    e[++cnt].nxt = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
void bfs(){
    queue<pii> que;
    que.push({1, 0});
    while(!que.empty()){
        pii tmp = que.front(); que.pop();
        int u = tmp.first, step = tmp.second;
        level = max(level, step);
        if(head[u]){
            for(int i = head[u]; i; i = e[i].nxt)
                que.push({e[i].to, step+1});
        }
        else ans[step]++;
    }
}
int main(){
    scanf("%d%d", &n, &m);
    while(m--){
        scanf("%d%d", &par, &k);
        while(k--){
            scanf("%d", &child);
            add(par, child);
        }
    }
    bfs();
    for(int i = 0; i <= level; i++){
        printf("%d", ans[i]);
        if(i!=level) printf(" ");
    }
}

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <set>
#define ll long long
#define inf 0x3f3f3f
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int maxn = 1e4+100; 
int n, m, s, cnt;
int val[maxn], fa[maxn];
int t, head[maxn];
vector<int> path[maxn];
struct node{
    int to, nxt;
}e[maxn];
//bool cmp(vector<int> a, vector<int> b){
//    reverse(a.begin(), a.end());
//    reverse(b.begin(), b.end());
//    return 
//}
void add(int u, int v){
    e[++t].to = v;
    e[t].nxt = head[u];
    head[u] = t;
}
void dfs(int u, int sum){
    if(!head[u]&&sum==s) {
        while(u!=-1) path[cnt].pb(val[u]), u = fa[u];
        reverse(path[cnt].begin(), path[cnt].end());
        cnt++;
    }
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if(v==fa[u]) continue;
        dfs(v, sum+val[v]);
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 0; i <= n-1; i++) scanf("%d", &val[i]);
    fa[0] = -1;
    while(m--){
        int u, v, k;
        scanf("%d%d", &u, &k);
        while(k--){
            scanf("%d%", &v);
            add(u, v), fa[v] = u;
        }
    }
    dfs(0, val[0]);
    sort(path, path+cnt);
    for(int i = cnt-1; i >= 0; i--) {
        int len = path[i].size();
        for(int j = 0; j < len; j++)
            cout << path[i][j] << (j==len-1 ? "" : " ");
        cout << endl;
    }
}