Codeforces ラウンド #245 (ディビジョン 1)??Xor-tree_html/css_WEB-ITnose

質問リンク

質問の意味:
n 個のノードを持つツリーがある場合、1 はルート ノードです。操作は、ノード x を選択し、現在の値、x の孫、および孫の孫を反転することです。 。 。すべてを否定します
次に、各点の初期値と各点の最終目標値を伝え、操作の数が最も少ないときに選択する必要があるノードを見つけます
(1?≤?n?≤?105)

分析:
深さの浅いポイントは最も影響を受けないはずです (ルート ノードはそれ自体によってのみ影響を受けます)。そのため、ルートから下方向に再帰的に処理できます

const int MAXN = 110000;VI G[MAXN], ans;int now[MAXN], goal[MAXN];void dfs(int u, int fa, int a, int b){	int rev = ((now[u] ^ a) != goal[u]);	if (rev) 	{		ans.push_back(u);		a ^= 1;	}	REP(i, G[u].size())	{		int v = G[u][i];		if (v != fa)			dfs(v, u, b, a);	}}int main(){	//    freopen("in.txt", "r", stdin);	int n, a, b;	while (~RI(n))	{		FE(i, 0, n) G[i].clear();		ans.clear();		REP(i, n - 1)		{			RII(a, b);			G[a].push_back(b);			G[b].push_back(a);		}		FE(i, 1, n) RI(now[i]);		FE(i, 1, n) RI(goal[i]);		dfs(1, 0, 0, 0);		WI(ans.size());		REP(i, ans.size())			WI(ans[i]);	}	return 0;}