原题链接
考察:DFS
思路:
\(mod[i]\)维护\(i\)结点是否被修改,\(anc[i]\)记录\(i\)结点的父节点的父节点是谁.直接一次DFS即可同时求出两个值.
Code
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100010;
struct Road{
int ne,to;
}road[N<<1];
int n,h[N],idx,goal[N],source[N],res;
int anc[N],mod[N],ans[N],cnt;
void add(int a,int b)
{
road[idx].to = b,road[idx].ne =h[a],h[a] = idx++;
}
void dfs(int u,int fa)
{
if(goal[u]!=source[u])
{
if(!mod[anc[u]]) res++,ans[++cnt] = u;
mod[u] = 1;//被修改了
source[u]^=1;
}else if(mod[anc[u]]) res++,ans[++cnt] = u;
for(int i=h[u];~i;i=road[i].ne)
{
int v = road[i].to;
if(v==fa) continue;
anc[v] = fa;
dfs(v,u);
}
mod[u] = 0;
}
int main()
{
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
for(int i=1;i<=n;i++) scanf("%d",&source[i]);
for(int i=1;i<=n;i++) scanf("%d",&goal[i]);
dfs(1,0);
printf("%d\n",res);
for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
return 0;
}