【題解】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 ===
lines = sys.stdin.readlines()
#with open("data.txt", "r") as f:
#    lines = f.readlines()

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)
分享本文 Share with friends