Heim > Web-Frontend > 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
Freigeben: 2016-06-24 12:04:45
Original
845 Leute haben es durchsucht

题目链接

  • 题意:
    给一棵树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;}
    Nach dem Login kopieren


    Verwandte Etiketten:
    Quelle:php.cn
    Erklärung dieser Website
    Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
    Beliebte Tutorials
    Mehr>
    Neueste Downloads
    Mehr>
    Web-Effekte
    Quellcode der Website
    Website-Materialien
    Frontend-Vorlage