Codeforces 832D(Misha, Grisha and Underground,LCA)
- 2020 年 5 月 17 日
- 筆記
- Codeforces
題意:在一棵生成樹上，給出了三個點，求三個點之間最大的相交點數，CF難度1900。
題解：求出三個lca，並取深度最大的那個，就是我們要的三岔路口K，然後分別求出K到a，b，c三點的路徑長度，取最大值+1就是答案。為什麼是取深度最大的呢？因為只有當深度是最大的時候設該點為K，這個K為三岔路口，每一個a，b，c到K的距離都不會用重複，否則如果取的不是最深的，可能造成重複的情況，這個需要避免。然後找到這個K之後，ans就是a，b，c三點分別到K的距離+1即可（+1是因為本身也算）。
一開始沒做出來的原因：不知道如何找這個岔口….以為需要把岔口當做root來弄，然後就需要一次又一次的重複更新建立LCA表，就很麻煩。其實求岔口只需要以1作為root，然後a，b，c三個點兩兩求LCA然後取深度最大的LCA就行了….樹上每2個點的距離dis(u,v)=depth[u]+depth[v]-2*depth(LCA(u,v)],好吧是我菜了
#include<bits/stdc++.h> #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl '\n' #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int tot,head[maxn]; struct E{ int to,next; }edge[maxn<<1]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int n,m,a[maxn],fa[maxn][40],depth[maxn],vis[maxn]; void dfs(int s,int step){ depth[s]=step;vis[s]=1; for(int i=head[s];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]) fa[v][0]=s,dfs(v,step+1); } } void bz(){ for(ll j=1;j<=30;j++){ for(ll i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } } ll LCA(ll u,ll v){ if(depth[u]<depth[v]) swap(u,v); ll dc=depth[u]-depth[v]; for(ll i=0;i<30;i++){ if((1<<i)&dc){ u=fa[u][i]; } } if(u==v) return u; for(ll i=29;i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } u=fa[u][0]; return u; } int dis(int u,int v){ return depth[u]+depth[v]-2*depth[LCA(u,v)]; } int main(){ scanf("%d%d",&n,&m);mem(head,-1); for(int i=2;i<=n;i++){ int x;scanf("%d",&x); add(i,x);add(x,i); } dfs(1,1); bz(); while(m--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); int l1=LCA(a,b); int l2=LCA(a,c); int l3=LCA(b,c); if(depth[l2]>depth[l1]) l1=l2; if(depth[l3]>depth[l1]) l1=l3; cout<<max(dis(l1,a),max(dis(l1,b),dis(l1,c)))+1<<endl; } }
View Code
