【bzoj1787】&【bzoj1832】[Ahoi2008]Meet 紧急集合 & 聚会

bzoj1787就是bzoj1832

bzoj1832 空间和时间少了一些。。。

求三个结点到一个结点距离之和最小的结点以及距离和

求出两两lca，其中有两个相同，答案则为另一个

感觉就是一大暴力。。。

 #include<algorithm>

 #include<iostream>

 #include<cstdlib>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 using namespace std;

 #define N 500010

 struct edge

 {

     int to,next;

 }e[N<<];

 int head[N<<];

 int cnt;

 int fa[N][],dep[N];

 bool vis[N];

 int n,q;

 int u,v,w;

 int p1,p2,p3;

 int t;

 int ans;

 void link(int x,int y)

 {

     e[++cnt]=(edge){x,head[y]};

     head[y]=cnt;

 }

 void dfs(int x)

 {

     vis[x]=;

     for (int i=;i<=;i++)

     {

         if (dep[x]<(<<i))

             break;

         fa[x][i]=fa[fa[x][i-]][i-];

     }

     for (int i=head[x];i;i=e[i].next)

     {

         int t=e[i].to;

         if (vis[t])

             continue;

         dep[t]=dep[x]+;

         fa[t][]=x;

         dfs(t);

     }

 }

 int lca(int x,int y)

 {

     if (dep[x]<dep[y])

         swap(x,y);

     int t=dep[x]-dep[y];

     for (int i=;i>=;i--)

         if (t & (<<i))

             x=fa[x][i];

     if (x==y)

         return x;

     for (int i=;i>=;i--)

         if (fa[x][i]!=fa[y][i])

             x=fa[x][i],y=fa[y][i];

     return fa[x][];

 }

 int dis(int x,int y)

 {

     int k=lca(x,y);

     return dep[x]+dep[y]-(dep[k]<<);

 }

 int main()

 {

     scanf("%d%d",&n,&q);

     for (int i=;i<n;i++)

     {

         scanf("%d%d",&u,&v);

         link(u,v);

         link(v,u);

     }

     dfs();

     while (q--)

     {

         scanf("%d%d%d",&u,&v,&w);

         p1=lca(u,v);

         p2=lca(u,w);

         p3=lca(v,w);

         if (p1==p2)

             t=p3;

         else if (p1==p3)

             t=p2;

         else

             t=p1;

         ans=dis(u,t)+dis(v,t)+dis(w,t);

         printf("%d %d\n",t,ans);

     }

     return ;

 }