zoj 3195(LCA加强版)

传送门:Problem 3195

https://www.cnblogs.com/violet-acmer/p/9686774.html

题意：

　　给一个无根树，有q个询问，每个询问3个点(a,b,c)，问将这3个点连起来，距离最短是多少。

题解：

　　我的思路：

　　　　(1)分别求出Lca(a,b),Lca(a,c),Lca(b,c);

　　　　(2)找到三个Lca( )中深度最深的那个节点（此处假设Lca(a,b)深度最深），设变量 res = dist[a]+dist[b]-2*dist[Lca(a,b)];

　　　　(3)求出Lca(a,b)与c的最近公共祖先，res += dist[c]+dist[Lca(a,b)]-2*dist[Lca(a,b,c)];

　　参考大佬题解思路：

　　　　分别求LCA(a,b),LCA(a,c),LCA(b,c)，和对应的距离，然后3个距离相加再除以2就是这个询问的结果。

AC代码：

　　晚上看了LCA的RMQ算法的一个题，改了一晚上，貌似理解了，太累了，明天再把这个代码的细节写一下.............

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<vector>
  4 #include<cstring>
  5 using namespace std;
  6 #define pb push_back
  7 #define ll long long
  8 #define mem(a,b) (memset(a,b,sizeof a))
  9 const int maxn=5e4+50;
 10 
 11 struct Node
 12 {
 13     int to;
 14     int weight;
 15     Node(int to,int weight):to(to),weight(weight){}
 16 };
 17 vector<Node >edge[maxn];
 18 int n,q;
 19 int fa[20][maxn];
 20 int dist[maxn];
 21 int depth[maxn];
 22 void addEdge(int u,int v,int w)
 23 {
 24     edge[u].pb(Node(v,w));
 25     edge[v].pb(Node(u,w));
 26 }
 27 void Init()
 28 {
 29     for(int i=0;i < n;++i)
 30         edge[i].clear();
 31 }
 32 void Dfs(int u,int f,int d,int l)
 33 {
 34     fa[0][u]=f;
 35     dist[u]=l;
 36     depth[u]=d;
 37     for(int i=0;i < edge[u].size();++i)
 38     {
 39         int to=edge[u][i].to;
 40         int w=edge[u][i].weight;
 41         if(to != f)
 42             Dfs(to,u,d+1,l+w);
 43     }
 44 }
 45 void Pretreat()
 46 {
 47     Dfs(0,-1,0,0);
 48     for(int k=0;k+1 < 20;++k)
 49         for(int u=0;u < n;++u)
 50             if(fa[k][u] == -1)
 51                 fa[k+1][u]=-1;
 52             else
 53                 fa[k+1][u]=fa[k][fa[k][u]];
 54 }
 55 int Lca(int u,int v)
 56 {
 57     if(depth[u] > depth[v])
 58         swap(u,v);
 59     int k;
 60     for(k=0;(1<<k) <= depth[v];++k);
 61     k--;
 62     for(int i=k;i >= 0;--i)
 63         if((depth[v]-(1<<i)) >= depth[u])
 64             v=fa[i][v];
 65     if(u == v)
 66         return v;
 67     for(int i=k;i >= 0;--i)
 68         if(fa[i][v] != -1 && fa[i][v] != fa[i][u])
 69         {
 70             v=fa[i][v];
 71             u=fa[i][u];
 72         }
 73     return fa[0][v];
 74 }
 75 int main()
 76 {
 77     bool flag=false;
 78     while(~scanf("%d",&n))
 79     {
 80         Init();
 81         if(flag)
 82             printf("
");
 83         flag=true;
 84         for(int i=1;i < n;++i)
 85         {
 86             int u,v,w;
 87             scanf("%d%d%d",&u,&v,&w);
 88             addEdge(u,v,w);
 89         }
 90         Pretreat();
 91         scanf("%d",&q);
 92         for(int i=1;i <= q;++i)
 93         {
 94             int a,b,c;
 95             scanf("%d%d%d",&a,&b,&c);
 96             int res;
 97             int lcaAB=Lca(a,b);
 98             int lcaAC=Lca(a,c);
 99             int lcaBC=Lca(b,c);
100             if(depth[lcaAB] > depth[min(lcaAC,lcaBC)])
101             {
102                 res=dist[a]-dist[lcaAB]+dist[b]-dist[lcaAB];
103                 res += dist[lcaAB]-dist[Lca(lcaAB,c)]+dist[c]-dist[Lca(lcaAB,c)];
104             }
105             else if(depth[lcaAC] > depth[min(lcaAB,lcaBC)])
106             {
107                 res=dist[a]-dist[lcaAC]+dist[c]-dist[lcaAC];
108                 res += dist[lcaAC]-dist[Lca(lcaAC,b)]+dist[b]-dist[Lca(lcaAC,b)];
109             }
110             else
111             {
112                 res=dist[b]-dist[lcaBC]+dist[c]-dist[lcaBC];
113                 res += dist[lcaBC]-dist[Lca(lcaBC,a)]+dist[a]-dist[Lca(lcaBC,a)];
114             }
115             printf("%d
",res);
116         }
117     }
118     return 0;
119 }

基于二分的LCA