Home > Web Front-end > HTML Tutorial > Codeforces Round #245 (Div. 1)??Xor-tree_html/css_WEB-ITnose

Codeforces Round #245 (Div. 1)??Xor-tree_html/css_WEB-ITnose

WBOY
Release: 2016-06-24 12:04:45
Original
846 people have browsed it

Question link

  • Question meaning:
    Given a tree with n nodes, 1 is the root node. The operation is to select a node x, invert the current value, the grandchild of x, and the grandchild of the grandchild. . . Negate all
    Now tell the initial value of each point and the final target value of each point, and find those nodes that need to be selected when the number of operations is minimum
    (1?≤?n?≤?105)
  • Analysis:
    Points with shallow depth must be the least affected (the root node is only affected by itself), so it can be processed recursively downward from the root
  • 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;}
    Copy after login


    Related labels:
    source:php.cn
    Statement of this Website
    The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
    Popular Tutorials
    More>
    Latest Downloads
    More>
    Web Effects
    Website Source Code
    Website Materials
    Front End Template