题目描述: 给一棵有n个点的有根树,点的编号为1到n,根为1。每个点的颜色是红色或者蓝色。对于树上的一个点,如果其子树中(不包括该点本身)红色点和蓝色点的数量相同,那么我们称该点是平衡的。 请你计算给定的树中有多少个点是平衡点。用C++写
时间: 2023-04-08 16:01:23 浏览: 120
抱歉,我可以回答这个问题。以下是C语言代码:
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100005
int n, ans;
int color[MAXN], balance[MAXN];
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], cnt;
void add_edge(int u, int v) {
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
}
void dfs(int u, int fa) {
int red = 0, blue = 0;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (v == fa) continue;
dfs(v, u);
red += color[v] == 1;
blue += color[v] == 2;
balance[u] += balance[v];
}
if (red == blue) {
balance[u]++;
ans++;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &color[i]);
if (color[i] == 1) color[i] = 2;
else if (color[i] == 2) color[i] = 1;
}
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
dfs(1, 0);
printf("%d\n", ans);
return 0;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)