倍增求LCA

LCA函数返回(u,v)两点的最近公共祖先

#include 
     
      using namespace std;const int N = 40010*2;struct node {    int v,val,next;    node(){}    node(int vv,int va,int nn):v(vv),val(va),next(nn){}}E[N];int n,m;int tot,head[N],dis[N],f[N][20],dep[N];void init() {    tot = 0;    memset(head,0,sizeof(head));    memset(dis,0,sizeof(dis));    memset(f,0,sizeof(f));    memset(dep,0,sizeof(dep));}void add(int u,int v,int val) {    E[++tot].next = head[u];    E[tot].v = v;    E[tot].val = val;    head[u] = tot;}void addEdge(int u,int v,int val) {    add(u,v,val);    add(v,u,val);}void dfs(int x,int fa) {    f[x][0] = fa;    for(int i=1;f[x][i-1];i++)        f[x][i] = f[f[x][i-1]][i-1];    for(int i=head[x]; i; i=E[i].next) {        int v = E[i].v;        if(v != fa) {            dis[v] = dis[x] + E[i].val;            dep[v] = dep[x] + 1;            dfs(v,x);        }    }}int lca(int u,int v) {    if(dep[u] < dep[v]) swap(u,v);    //int ans = dep[u] - dep[v];    for(int i=19;i>=0;i--)        if(dep[u]-(1<
      
       =dep[v])            u = f[u][i];    for(int i=19;i>=0;i--) {        if(f[u][i]!=f[v][i])            u=f[u][i],v=f[v][i];//ans+=(2<