邻接表(适合存储稀疏图:边数远小于点数的平方)
// 对于每个点k,开一个单链表,存储k所有可以走到的点。h[k]存储这个单链表的头结点
// 对于每个点k,每个idx,都有e[idx] == k成立,即每个k对应唯一确定的idx
// 假设节点k有n个邻接节点(A1, A2, ..., An), 则:
// A1的idx = h[k] = i1, A1的编号 = e[h[k]]
// A2的idx = ne[i1] = i2, A2的编号 = e[ne[i1]]
// .....................................
// An的idx = ne[i(n-1)], An的编号 = e[ne[i(n-1)]]
const int N = 1010, M = 10010;
int h[N], e[M], ne[M], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
dfs
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int c[N];
int h[N], e[N], ne[N], idx;
int ans = 1;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int a)
{
for (int i = h[a]; ~ i; i = ne[i])
{
if (c[e[i]] != c[a]) ans ++ ;
dfs(e[i]);
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 2; i <= n; i ++ )
{
int t;
cin >> t;
add(t, i);
}
for (int i = 1; i <= n; i ++ ) cin >> c[i];
dfs(1);
cout << ans << endl;
return 0;
}
bfs
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 10010;
int n;
int c[N];
int h[N], e[N], ne[N], idx;
int ans = 1;
queue<int> q;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs(int a)
{
q.push(a);
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (c[j] != c[t]) ans ++ ;
q.push(j);
}
}
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 2; i <= n; i ++ )
{
int t;
cin >> t;
add(t, i);
}
for (int i = 1; i <= n; i ++ ) cin >> c[i];
bfs(1);
cout << ans << endl;
return 0;
}
不建树
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int c[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 >> c[i];
int res = 1;
for (int i = 2; i <= n; i ++ )
if (c[i] != c[p[i]])
res ++ ;
cout << res << endl;
return 0;
}