⿊⽩翻转

题目描述

⼩杨有⼀棵包含 个节点的树，这棵树上的任意⼀个节点要么是⽩⾊，要么是⿊⾊。⼩杨认为⼀棵树是美丽树当且 仅当在删除所有⽩⾊节点之后，剩余节点仍然组成⼀棵树。 ⼩杨每次操作可以选择⼀个⽩⾊节点将它的颜⾊变为⿊⾊，他想知道⾃⼰最少要执⾏多少次操作可以使得这棵树变 为美丽树。

输入格式

第⼀⾏包含⼀个正整数 ，代表树的节点数。 第⼆⾏包含 个⾮负整数 ，其中如果 ，则节点 的颜⾊为⽩⾊，否则为⿊⾊。 之后 ⾏，每⾏包含两个正整数 ，代表存在⼀条连接节点 和 的边。

输出格式

输出⼀个整数，代表最少执⾏的操作次数。 3.1.4 样例1 1 5 2 0 1 0 1 0 3 1 2 4 1 3 5 3 4 6 3 5 1 2 3.1.5 样例解释 将节点 和 变为⿊⾊即可使这棵树变为美丽树，此时删除⽩⾊节点 ，剩余⿊⾊节点仍然组成⼀棵树。 3.1.6 数据范围 子任务编号 数据点占比 特殊条件 1 30% 树的形态为⼀条链 2 30% 只有两个节点颜⾊为⿊⾊ 3 40% 对于全部数据，保证有 ， 。 3.1.7 参考程序 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 vector g[N]; 5 int col[N],num[N]; 6 int ans,sum; 7 void calc(int x,int fa){ 8 num[x]+=col[x]; 9 for(auto i:g[x]){ 10 if(i!=fa){ 11 calc(i,x); 12 num[x]+=num[i]; 13 } 14 } 15 } 16 void dfs(int x,int fa){ 17 int fl=0; 18 if(num[x]!=sum&&num[x]!=0)fl=1; 19 for(auto i:g[x]){ 20 if(i!=fa){ 21 dfs(i,x); 22 if(num[i]!=0&&num[i]!=num[x]-col[x]){ 23 fl=1; 24 } 25 } 26 } 27 if(fl==1&&col[x]!=1)ans++; 28 } 29 int main(){ 30 int n; 31 cin>>n; 32 for(int i=1;i<=n;i++){ 33 cin>>col[i]; 34 sum+=col[i]; 35 } 36 for(int i=1;i<n;i++){ 37 int u,v; 38 cin>>u>>v; 39 g[u].push_back(v); 40 g[v].push_back(u); 41 } 42 calc(1,0); 43 dfs(1,0); 44 cout<<ans<<"\n"; 45 }

样例输入 #1

1 5
2 0 1 0 1 0
3 1 2
4 1 3
5 3 4
6 3 5
1 2

样例输出 #1

样例解释 #1

将节点 和 变为⿊⾊即可使这棵树变为美丽树，此时删除⽩⾊节点 ，剩余⿊⾊节点仍然组成⼀棵树。

数据范围

子任务编号 数据点占比 特殊条件 1 30% 树的形态为⼀条链 2 30% 只有两个节点颜⾊为⿊⾊ 3 40% 对于全部数据，保证有 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。