<=给个免费的赞,球球啦QWQ
本题解代码十分简洁!
第一次AKKK(因为手速等原因在T2上卡了好久QWQ
这道题是真的淼
简单到爆炸啊...
题目描述
给定一个 n 个节点的树,节点编号为 1∼n
1 号节点是树的根节点。
初始时,所有节点的颜色均为 0。
现在,你需要对该树进行重新染色,其中节点 i 的目标颜色为 ci。
每次染色操作的具体流程如下:
选择一个节点 v 和一种颜色 x。
将以节点 v 为根节点的子树中的全部节点(包括节点 v)都染成颜色 x。
请你计算,为了使得每个节点都被染成目标颜色,至少需要进行多少次染色操作。
输入样例
6
1 2 2 1 5
2 1 1 1 1 1
输出样例
3
算法
通过观察样例我们发现:
如果c[i] = c[p[i]]那么:
刷根节点就可以了,不需要再刷i
例如我们要刷一个根节点为a的子树
有一个子节点为b
那么当刷完整个子树,只需要考虑b的子树和a的其他子树就行了
所以,我瞎蒙了一个结论
假设ans = n,那么:
当c[i] = c[p[i]]时,ans –;
2022/07/03:更新分析:
从1开始递归以下步骤:
1.首先,我们观察某个树的根节点
2.显然,根节点的父亲一定颜色已经染好了
3.根节点是一定要刷的,且显然第一个刷(要不然就有一些白刷了)
4.然后观察根节点的子树,回到第一步
复杂度线性$O(n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200009;
int a[N], f[N], n, p[N];
int main() {
cin >> n;
for(int i = 2;i <= n;++ i) cin >> p[i];
for(int i = 1;i <= n;++ i) cin >> a[i];
int ans = n;
for(int i = 2;i <= n;++ i)
if(a[i] == a[p[i]]) ans --;
cout << ans << endl;
return 0;
}
写完以后直呼好家伙
代码是真的简洁!
沉默了
阿巴阿巴
666