牛牛的树

NC21629. 牛牛的树

描述

牛牛有一棵标号为0到n-1的树，他用一个p数组来描述这棵树，p[i]表示p[i]与i+1之间有一条无向边

树的每一条边上都有一盏灯，每个灯都有开与关两种状态，边的编号为0到n-2，第i条边连接p[i]与(i+1)
有些边对你来说是非常重要的，你的目标是点亮所有这些边上的灯

你能做的操作是每次选择一条路径，将路径上的灯的状态取反。

输出最少需要的操作次数

输入描述

第一行输入一个整数n(2 ≤ n ≤ 50)

第二行输入n - 1个整数p[i]（0 ≤ i ≤ n-2）, 表示p[i]与i+1之间有一条边，0 ≤ p[i] ≤ i

第三行输入一个长度为n-1的01串表示每条边上灯的状态

第四行输入一个长度为n-1的01串表示每条边是否重要

输出描述

输出一个整数

示例1

输入:

输出:

说明:

示例2

输入:

7
0 0 1 1 4 4
000100
111111

输出:

说明:

示例3

输入:

50
0 0 1 2 4 4 6 1 2 5 2 8 8 3 6 4 14 7 18 14 11 7 1 12 7 5 18 23 0 14 11 10 2 2 6 1 30 11 9 12 5 35 25 11 23 17 14 45 15
0000000000010000000000000010000010100000000000000
1010111111111011011111000110111111111111111110111

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2020-09-29 19:36:21

#include<iostream>
#include<cstdio>
using namespace std;
#define N 100127
int n,a[N],b[N],c[N],d[N],fa[N],ans=0;char sc[N];
int main(){
	scanf("%d",&n);int i;for(i=2;i<=n;i++)scanf("%d",&fa[i]),++fa[i];
	scanf("%s",sc+1);for(i=2;i<=n;i++)a[i]=sc[i-1]-'0';
	scanf("%s",sc+1);for(i=2;i<=n;i++)d[i]=sc[i-1]-'0';
	for(i=n;i>=2;i--){if(d[i]&&(!(a[i]^b[i])))c[i]=1;b[fa[i]]^=b[i]^c[i];}
	for(i=2;i<=n;i++)ans+=c[i];printf("%d",(ans+1)>>1);return 0;
}

上一题

下一题

详情