Rumah > hujung hadapan web > 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
Lepaskan: 2016-06-24 12:04:45
asal
846 orang telah melayarinya

题目链接

  • 题意:
    给一棵树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;}
    Salin selepas log masuk


    Label berkaitan:
    sumber:php.cn
    Kenyataan Laman Web ini
    Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
    Tutorial Popular
    Lagi>
    Muat turun terkini
    Lagi>
    kesan web
    Kod sumber laman web
    Bahan laman web
    Templat hujung hadapan