代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    static List<List<Integer>> tree;
    static int[] values;
    static int count = 0;
    static boolean[] used;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // 构建树
        tree = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }
        
        // 读取父节点信息
        String[] parents = br.readLine().split(" ");
        for (int i = 2; i <= n; i++) {
            int parent = Integer.parseInt(parents[i-2]);
            tree.get(parent).add(i);
        }
        
        // 读取节点权值
        values = new int[n + 1];
        String[] vals = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            values[i] = Integer.parseInt(vals[i-1]);
        }
        
        // 找出最大权值，用于初始化used数组
        int maxValue = 0;
        for (int i = 1; i <= n; i++) {
            maxValue = Math.max(maxValue, values[i]);
        }
        
        used = new boolean[maxValue + 1];
        
        // 计算所有合法路径
        for (int i = 1; i <= n; i++) {
            dfs(i);
        }
        
        System.out.println(count);
    }
    
    static void dfs(int node) {
        // 如果当前节点权值已存在于路径中，则不合法
        if (used[values[node]]) {
            return;
        }
        
        // 当前节点加入路径，计数加1
        used[values[node]] = true;
        count++;
        
        // 继续向子节点探索
        for (int child : tree.get(node)) {
            dfs(child);
        }
        
        // 回溯，移除当前节点权值
        used[values[node]] = false;
    }
}

Python

def main():
    n = int(input())
    
    # 读取父节点信息
    parents = [0] + list(map(int, input().split()))
    
    # 构建树
    tree = [[] for _ in range(n + 1)]
    for i in range(2, n + 1):
        tree[parents[i-1]].append(i)
    
    # 读取节点权值
    values = [0] + list(map(int, input().split()))
    
    count = 0
    
    def dfs(node, value_set):
        nonlocal count
        
        # 如果当前节点权值已存在于路径中，则不合法
        if values[node] in value_set:
            return
        
        # 当前节点加入路径，计数加1
        value_set.add(values[node])
        count += 1
        
        # 继续向子节点探索
        for child in tree[node]:
            dfs(child, value_set.copy())
    
    # 从每个节点开始，计算所有合法路径
    for i in range(1, n + 1):
        dfs(i, set())
    
    print(count)

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<vector<int>> tree;
vector<int> values;
int count = 0;

void dfs(int u, unordered_set<int> valueSet) {
    // 如果当前节点权值已存在于路径中，则不合法
    if (valueSet.find(values[u]) != valueSet.end()) {
        return;
    }
    
    // 当前节点加入路径，计数加1
    valueSet.insert(values[u]);
    count++;
    
    // 继续向子节点探索
    for (int v : tree[u]) {
        dfs(v, valueSet);
    }
}

int main() {
    int n;
    cin >> n;
    
    // 构建树
    tree.resize(n + 1);
    
    // 读取父节点信息
    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        tree[parent].push_back(i);
    }
    
    // 读取节点权值
    values.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> values[i];
    }
    
    // 计算所有合法路径
    for (int i = 1; i <= n; i++) {
        unordered_set<int> valueSet;
        dfs(i, valueSet);
    }
    
    cout << count << endl;
    return 0;
}