f161 - 3. 尋寶之旅
題目描述
題目給定一棵樹，每個節點都有一個數值。要求找到樹中出現次數最多的數值，並輸出其最大出現次數。
解題思路
這題可以使用深度優先搜尋 (DFS) 來遍歷樹。在 DFS 的過程中，使用一個 map 來記錄每個數值出現的次數。每次訪問一個節點時，將該節點的數值在 map 中出現次數加一，並更新最大出現次數。在回溯時，將該節點的數值在 map 中出現次數減一。這樣可以確保在遍歷完整個樹後，map 中記錄的是每個數值在整個樹中出現的次數。
複雜度分析
- 時間複雜度: O(n)，其中 n 是樹的節點數量。DFS 遍歷所有節點一次，map 的插入和查找操作平均時間複雜度為 O(1)。
- 空間複雜度: O(n)，其中 n 是樹的節點數量。map 最多可能存儲所有節點的數值，因此空間複雜度為 O(n)。此外，DFS 的遞迴調用棧深度也可能達到 O(n)。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,a[200005],ans,x,y;
map <int,int> mp;
vector <int> e[200005];
void dfs(int x){
mp[a[x]]++;
ans=max(ans,mp[a[x]]);
for(int i=0;i<e[x].size();++i){
dfs(e[x][i]);
}
mp[a[x]]--;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n;
for(int i=0;i<n;++i){
cin >> a[i];
}
for(int i=0;i<n-1;++i){
cin >> x >> y;
e[x].push_back(y);
}
dfs(0);
cout << ans;
}