首页 > 代码库 > A. Xor-tree
A. Xor-tree
题目意思：
给一颗n个节点的树，每个节点有一个值要么是0要么是1，改变某个节点的值时，它的儿子不变，它儿子的儿子翻转，它儿子的儿子的儿子不变，如此类推。给定各个节点的目标值，求最少的翻转次数，使得达到要求。
题解思路：
贪心+Dfs
判断当前节点的值，与目标值比较
1.当前节点值由其上上一个节点值是否需要改变决定。
2.Dfs每次传参p1，p2表示上前两层的节点改变。
（通过p1，p2的交换，实现间隔改变节点值，同时实现累加的改变值）
#include<stdio.h>#include<vector>using namespace std;const int MAX = 100100;vector<int>edge[MAX];bool init[MAX];bool goal[MAX];int num;int ans[MAX];void Dfs(int cur,int p1,int p2,int fa){ if(init[cur]^p1!=goal[cur]) { ans[num++]=cur; //printf("tmp:%d\n",cur); p1=1-p1; } for(int i=0;i<edge[cur].size();i++) { if(edge[cur][i]==fa)continue; Dfs(edge[cur][i],p2,p1,cur); }}int main(){ int n; int i,j; int x,y; while(scanf("%d",&n)!=EOF) { for(i=1;i<n;i++) edge[i].clear(); for(i=1;i<n;i++) { scanf("%d %d",&x,&y); edge[x].push_back(y); edge[y].push_back(x); } for(i=1;i<=n;i++) scanf("%d",&init[i]); for(i=1;i<=n;i++) scanf("%d",&goal[i]); num=0; Dfs(1,0,0,0); printf("%d\n",num); for(i=0;i<num;i++) printf("%d\n",ans[i]); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。