题解 | #好子树#

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

int dfs(int p,vector<vector<int>> &edges,vector<int> &nums,int &maxnum,int &minnum){
    int ma=nums[p],mi=nums[p],n=0;
    for(auto a:edges[p]) n+=dfs(a,edges,nums,ma,mi);
    maxnum=max(maxnum,ma);
    minnum=min(minnum,mi);
    if((ma-mi)%2==1){
        n++;
        nums[p]=-1;
    }
    return n;
}

int main() {
    int n,u,v;
    cin>>n;
    vector<int> nums(n);
    vector<vector<int>> edges(n);
    for(int i=0;i<n;i++) cin>>nums[i];
    while(cin>>u>>v) edges[u-1].emplace_back(v-1);
    int maxnum=nums[0],minnum=nums[0];
    cout<<dfs(0,edges,nums,maxnum,minnum)<<endl;
    for(int i=0;i<n;i++) if(nums[i]==-1) cout<<i+1<<' ';
    return 0;
}

利用dfs深度优先搜索解题。nums数组存储节点权值，edges二维数组存储边。对于一个节点，搜索其下一节点，并返回子树的最大最小值。若差值为奇数则为将该节点p标记（可直接将nums[p]赋值为-1来标记以节省空间，反正后续也不再需要用到p的权值）