【題解】ZeroJudge f161: 3. 尋寶之旅

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=f161
【解題想法】DFS

```#include <iostream>
#include <vector>
#include <map>
using namespace std;

int n, c[200005], a, b, ans;

vector <int> v[200005];
map <int, int> mp;

void dfs(int now){
mp[ c[now]]++;
ans = max(ans, mp[ c[now]]);
for (auto i:v[now]){
dfs(i);
}
mp[ c[now]]--;
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++){
cin >> c[i];
}
for (int i = 1; i < n; i++){
cin >> a >> b;
a++;
b++;
v[a].push_back(b);
}
dfs(1);
cout << ans << "\n";
}
```

Python code (credit: Amy Chou, 8/30/2020)

```import sys

def dfs(now):
global mp
mp[c[now]] = mp.get(c[now], 0) + 1

global ans
ans = max(ans, mp[c[now]])
for i in v[now]:
dfs(i)
mp[c[now]] -= 1

# === main ===
#with open("data.txt", "r") as f:

data = []
for line in lines:
data.extend(list(map(int, line.split())))

n = data[0]
c = data[1:n+1]
v = [[] for _ in range(n)]

for i in range(n-1):
#以防測資不是合法的樹
try:
a, b = data[n+1+i*2], data[n+1+i*2+1]
v[a].append(b)
except:
break

mp = {}
ans = 0
dfs(0)
print(ans)
```