无聊弄出来的Lca算法。。。

   天天在弯销油西。。。颓废万分。。晚上总算去水了道题。。我无聊中想出一个很SB的Lca。。。
就是把这颗树树链剖分(不用线段树的,只需要记录每个点对应当路径的最高点)。。。
然后考虑u和v的Lca(假设u的深度大于v)。。如果在同一条链中就是v。。
否则的话设u的路径最高点要深于v的路径最高点,那么显然Lca不可能在u的路径中,将u换成u的路径最高点的父节点。。。然后就这递归下去。。。
额。。时间复杂度LogN。。预处理复杂度是O(N)的。。常数又比线段树那个要小。。速度比记录2^k祖先那个和线段树都要快一些。。树链剖分还可以写Bfs..拒绝爆stack。。还是挺不错滴(*^__^*) 嘻嘻。。。
Code:(题目是Ural上的Tree)
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=50000;
using namespace std;
int n,q;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void AddEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));
E[t].pb(Edge(s,c));
}
void Init()
{
scanf("%d",&n);int s,t,c;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);
AddEdge(s,t,c);
}
}
int D[maxn],C[maxn],F[maxn],Size[maxn];
int Q[maxn],h,t,Own[maxn];
void BFS(int vs)
{
h=t=0;
for(Q[t++]=vs,F[vs]=-1,D[vs]=0,C[vs]=0;h<t;h++)
{
int x=Q[h];
tr(e,E[x])if(e->t!=F[x])
{
F[e->t]=x;C[e->t]=C[x]+e->c;
D[e->t]=D[x]+1;Q[t++]=e->t;
}
}
for(int i=h-1;i>=0;i–)
{
int x=Q[i];Size[x]=1;
tr(e,E[x])if(e->t!=F[x])Size[x]+=Size[e->t];
}
memset(Own,-1,sizeof Own);
for(int i=0;i<h;i++)
{
int a=Q[i];
int x=a,next;if(Own[x]>=0)continue;
for(;;x=next)
{
next=-1;Own[x]=a;
tr(e,E[x])if(e->t!=F[x])
if(next==-1||Size[e->t]>Size[next])
next=e->t;
if(next==-1)break;
}
}
}
int Lca(int u,int v)
{
for(;;)
{
if(D[u]<D[v])swap(u,v);
if(Own[u]==Own[v])return v;
if(D[Own[u]]<D[Own[v]])swap(u,v);
u=F[Own[u]];
}
}
int Query(int u,int v)
{
int lca=Lca(u,v);
return C[u]+C[v]-2*C[lca];
}
void Solve()
{
scanf("%d",&q);int u,v;
rep(i,q)
{
scanf("%d%d",&u,&v);
printf("%dn",Query(u,v));
}
}
int main()
{
//freopen("in","r",stdin);
Init();
BFS(0);
Solve();
}

7 thoughts on “无聊弄出来的Lca算法。。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>