思想
一种链表和哈希表结合的写法。
代码
import java.io.*;
import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = (int)1e5+5;
static long ans = 0;
static ArrayList<Integer>[] g= new ArrayList[N]; //存图
static Map<Integer, List<Integer>> map = new HashMap<>();//存储每次访问权值a[u]出现的最近深度
static int[] a = new int[N];
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static void dfs(int u, int dep, int maxx){
//更新最近的a[u]的深度
if(map.containsKey(a[u]) && !map.get(a[u]).isEmpty()){
int sz = map.get(a[u]).size();
maxx = Math.max(maxx, map.get(a[u]).get(sz-1));
}
ans += (dep-maxx); //深度1~深度3的合法路径就贡献了3-1条路径
//记录a[u]出现的路径
if(!map.containsKey(a[u])) map.put(a[u], new ArrayList<>());
map.get(a[u]).add(dep);
//开始遍历其子节点
for(Integer i : g[u]) dfs(i, dep+1, maxx);
int sz = map.get(a[u]).size();
map.get(a[u]).remove(sz-1); //回溯
}
public static void main(String[] args)throws IOException{
int n = nextInt();
for(int i=0; i<N; i++) g[i] = new ArrayList<>();
for(int i=2; i<=n; i++) {int x = nextInt(); g[x].add(i);}
for(int i=1; i<=n; i++) a[i] = nextInt();
dfs(1, 1, 0);
out.println(ans);
out.flush();
out.close();
}
}