http://poj.org/problem?id=1330

題解：LCA

樹上倍增

/* *@Author: STZG *@Language: C++ */ //#include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=10000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v,c; int ans,cnt,flag,temp,tot,sum,num; int pre[N]; bool vis[N]; int dep[N]; int dp[N][21]; string str,str1; struct node{int v,w; }x; vector<int>G[N]; int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);} void marge(int u,int v){int tu=find(u);int tv=find(v);if(tu!=tv){pre[tu]=tv;} } void dfs(int u){vis[u]=1;for(int i=0,j=G[u].size();i<j;i++){int v=G[u][i];if(!vis[v]){dep[v]=dep[u]+1;dp[v][0]=u;dfs(v);}} } void init(){for(int i=1;i<=n;i++){G[i].clear();pre[i]=i;}memset(vis,0,sizeof(vis));memset(dep,0,sizeof(dep));memset(dp,0,sizeof(dp));cnt=0,num=0; } int LCA(int x,int y){if(dep[x]<dep[y])swap(x,y);//cout<<x<<" "<<dp[1][0]<<endl;while(dep[x]>dep[y])x=dp[x][(int)log2(dep[x]-dep[y])];if(x==y)return x;for(int i=log2(dep[x]);i>=0;i--){if(dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i];}return dp[x][0]; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);scanf("%d",&t);while(t--){scanf("%d",&n);init();for(int i=1;i<n;i++){scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);marge(v,u);}//cout<<"1"<<endl;for(int i=1;i<=n;i++){if(pre[i]==i){dfs(i);}}//cout<<"2"<<endl;for(int i=0;i<20;i++){for(int j=1;j<=n;j++){dp[j][i+1]=dp[dp[j][i]][i];}}scanf("%d%d",&u,&v);cout<<LCA(u,v)<<endl;}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Nearest Common Ancestors的全部內容，希望文章能夠幫你解決所遇到的問題。

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