首页 > 代码库 > Codeforces Round #245 (Div. 1)——Xor-tree
Codeforces Round #245 (Div. 1)——Xor-tree
题目链接
- 题意:
给一棵树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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。