題目鏈接：點擊查看

題目大意：給出一個層層嵌套的樹狀結構，可以從某一點通過一個操作直接到達任意一個子節點的位置，但如果要從某個節點到達其祖先節點需要一層一層往上爬，問若要從節點A到達節點B，需要多少步

題目分析：LCA模板題，需要修改的地方就是當節點B就是LCA的時候特判一下，然后直接用deep數組計算就行了

注意一下多組輸入map記得清零，一開始忘清零，MLE了兩發。。太蠢了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;unordered_map<string,int>mp;int n,m,limit;vector<int>node[N];int du[N];int deep[N],dp[N][20];void dfs(int u,int f,int dep) {deep[u]=dep;dp[u][0]=f;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=0;i<node[u].size();i++)dfs(node[u][i],u,dep+1); }int LCA(int x,int y) {if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0]; }void init() {memset(du,0,sizeof(du));for(int i=1;i<=n;i++)node[i].clear();limit=log2(n)+1;mp.clear(); }int main() { // freopen("input.txt","r",stdin);ios::sync_with_stdio(false);int w;cin>>w;while(w--){cin>>n>>m;init();int cnt=0;for(int i=1;i<n;i++){string a,b;cin>>a>>b;if(!mp[a])mp[a]=++cnt;if(!mp[b])mp[b]=++cnt;node[mp[b]].push_back(mp[a]);du[mp[a]]++;}for(int i=1;i<=n;i++)//找入度為0的點作為根節點if(!du[i]){dfs(i,i,0);break;}while(m--){string a,b;cin>>a>>b;int lca=LCA(mp[a],mp[b]);int ans;if(lca==mp[b])//特判一下終點ans=0;elseans=1;ans+=deep[mp[a]]-deep[lca];printf("%d\n",ans);}}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 4547 CD操作(LCA模板)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。