目錄
一、題目
二、思路
1.? 問題轉化：同步DFS走樹
2.? 優化：同步DFS匹配
3.? 狀態設計：dfs參數含義
4.? 匹配過程：用 map 建立權值索引
5.? 終止條件：無法匹配則更新答案
6. 總結
?三、完整代碼
四、知識點總結
1. 鄰接表建樹
?2. DFS模板（樹）
3. map統計映射
?五、優化建議
一、題目
題目鏈接：藍橋杯2024年第十五屆省賽真題-團建 - C語言網
標簽：樹、DFS、映射、最長公共前綴
【題目抽象過來就是】：
-
兩棵樹分別從根結點1出發
-
每棵樹走一條路徑，從根走到葉子
-
只要路徑上對應位置的權值一致，前綴繼續，直到不一致
-
求任意一對路徑中最長的公共前綴長度
【等價描述】：
從樹1的結點i和樹2的結點j同時出發，若其子節點中存在相同權值的點，則同步走向下一個匹配點，繼續搜索；否則終止，更新答案
二、思路
本質上就是是樹上路徑問題，目標是找出兩棵樹中一對路徑，其權值前綴最長，且兩個路徑需從根走到某個葉子
1.? 問題轉化：同步DFS走樹
我們將這個“團建”問題轉化為更形式化的問題：
-
設第一棵樹為 T1?，第二棵樹為 T2
-
從T1的根結點（編號 1）出發，走到任意葉節點形成一個權值路徑 P1
-
從T2 的根結點（編號 1）出發，走到任意葉節點形成另一個權值路徑 P2
-
目標是找出一對路徑 P1?, P2，使它們的最長公共前綴（權值完全相同）長度最大
這個問題很容易想到暴力做法，枚舉所有從根到葉的路徑組合，比較公共前綴，但這會非常低效，因為路徑組合的數量是指數級的
2.? 優化：同步DFS匹配
我們注意到只要兩棵樹當前所在的節點權值一致，就可以繼續嘗試向下匹配，于是我們可以設計一個雙樹同步DFS的過程：
-
從兩棵樹的根結點出發（必須權值相同才開始）；
-
進入遞歸函數
dfs(i, j, pi, pj, cnt)，表示當前在第一棵樹的結點i，第二棵樹的結點j，pi、pj是其父節點，用于避免走回頭路； -
當前的公共前綴長度為
cnt； -
然后嘗試“配對子節點”：
-
對
i的所有子節點（除了父節點）建立map<int,int>表（key=權值，value=結點編號）； -
遍歷
j的所有子節點（同樣跳過父節點），如果它的權值在上面的 map 中出現，說明兩個子節點具有相同的權值； -
則遞歸調用
dfs(新i, 新j, i, j, cnt + 1)，繼續向下探索；
-
-
若當前無法繼續匹配，說明一條公共前綴路徑終止，更新
ans = max(ans, cnt)
這其實相當于構造了一個“公共路徑樹”：每次 DFS 都在嘗試走向匹配路徑的更深層
3.? 狀態設計：dfs參數含義
dfs(i, j, pi, pj, cnt)
-
i,j：當前分別在兩棵樹的哪個結點 -
pi,pj：各自結點的父結點，用于防止重復訪問（因為樹是無向圖） -
cnt：當前公共前綴的長度，也就是成功“匹配”的層數
每次進入 dfs，相當于說：“我已經找到了
cnt層的共同路徑，現在看看是否能進入下一層”
4.? 匹配過程：用 map 建立權值索引
由于要找到第二棵樹某個子節點的權值是否和第一棵樹子節點的權值相同，為了快速判斷和定位，我們用 map<int, int> 來做映射
map<int, int> m;
for (int newi : edge1[i]) {if (newi == pi) continue; //避免回頭m[c[newi]] = newi; //權值 → 節點編號
}
然后對于 j 的所有子節點，判斷它們的權值是否在 m 中出現：
for (int newj : edge2[j]) {if (newj == pj) continue;if (m.count(d[newj])) {//匹配成功，進入下一層dfs(m[d[newj]], newj, i, j, cnt + 1);}
}
這種方式效率高，而且靈活地實現了“同步匹配”的過程
5.? 終止條件：無法匹配則更新答案
一旦某一層匹配失敗（即 j 的子節點權值無法在 i 的子節點中找到對應值），這條同步路徑就結束了，此時需要更新全局最大值：
ans = max(ans, cnt);
這句代碼放在 DFS 末尾，保證所有路徑嘗試都會記錄最長前綴
6. 總結
-
我們不需要預先構造所有路徑
-
只需從根節點出發，通過匹配下一層的子節點權值，構造公共前綴路徑（相當于剪枝）
-
整個過程由 DFS 驅動，使用
map或unordered_map快速匹配子結點 -
最終輸出最長的前綴長度
ans
?三、完整代碼
#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N=2e5+10;
int n,m;
int c[N];//第一棵樹的權值
int d[N];//第二棵樹的權值
vector<vector<int>> edge1(N);//第一棵樹鄰接表,大小為N，存儲的類型為vector
vector<vector<int>> edge2(N);//第二棵樹
int ans=0;//i:第一棵樹的當前節點
//j:第二棵樹的當前節點
//pi:當前結點的父結點
//pj:同理
//cnt:當前前綴長度
void dfs(int i,int j,int pi,int pj,int cnt)
{//存儲第一棵樹的相鄰節點權值//first:權值，second：出現的次數 //map可以用來統計出現的次數 map<int,int>m; for(int newi:edge1[i]){//避免回頭走，父結點跳過 if(newi==pi) continue;//記錄權值對應位置 m[c[newi]]=newi;}//找第二棵樹 for(int newj:edge2[j]){if(newj==pj) continue;//碰到相同權值點，繼續向下走 //count統計的是次數 if(m.count(d[newj])){dfs(m[d[newj]],newj,i,j,cnt+1);}}//當前結點找不到相同權值，結束//更新答案ans=max(ans,cnt);return;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>c[i];for(int i=1;i<=m;i++) cin>>d[i];for(int i=1;i<=n-1;i++){int x,y;cin>>x>>y;edge1[x].push_back(y);edge1[y].push_back(x);}for(int i=1;i<=m-1;i++){int x,y;cin>>x>>y;edge2[x].push_back(y);edge2[y].push_back(x);}//根節點相同才能進入dfs if(c[1]==d[1]) dfs(1,1,-1,-1,1);cout<<ans;return 0;
}四、知識點總結
1. 鄰接表建樹
vector<vector<int>> tree(N);
tree[u].push_back(v);
tree[v].push_back(u); //因為是無向圖建樹
?2. DFS模板（樹）
void dfs(int u, int parent) {for (int v : tree[u]) {if (v == parent) continue;dfs(v, u);}
}
3. map統計映射
map<int, int> m;
m[val] = index; //記錄權值和對應結點編號
?五、優化建議
-
如果運行時常數過大，可以用
unordered_map替代map加快哈希效率 -
若題目限制非常緊，也可以采用前綴哈希或 Trie 樹進行路徑存儲優化
如果你覺得有收獲，歡迎點贊收藏支持！
后續將持續更新算法題解，也歡迎留言交流～
