题解 | #好子树#

# 使用dfs进行搜索 并记录当前子树的最大值
#

#include <algorithm>
#include <iostream>
#include <type_traits>
#include <vector>
using namespace std;

int n;
vector<int> ai;
vector<vector<int>> graph;
vector<int> res;

std::pair<int,int> dfs(int cur,int _min,int _max){
    int _cur_min = _min,_cur_max = _max;
    for(auto son : graph[cur]){
        auto t = dfs(son,_min,_max);
        _cur_min = min(_cur_min,t.first);
        _cur_max = max(_cur_max,t.second);
    }

    _max = std::max(ai[cur],_cur_max);
    _min = std::min(ai[cur],_cur_min);
    if((_max-_min)%2){
        res.push_back(cur);
    }
    return {_min,_max};
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    ai.resize(n);
    graph.resize(n);
    for(int i = 0 ; i < n ; i++){
        cin >> ai[i];
    }
    int root, sub;
    while(cin >> root && cin >> sub){
        graph[root-1].push_back(sub-1);   
    }
    dfs(0,1e9+1,0);
    std::cout << res.size() << std::endl;
    sort(res.begin(),res.end());
    for(auto it : res){
        cout << it+1 << " ";
    }
    cout << endl;
}
// 64 位输出请用 printf("%lld")