最近公共祖先LCA相关算法模板

问题描述：

倍增法求LCA

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <vector> #define CLOSE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); #define isd(c) ('0' <= (c) && (c) <= '9') #define isa(c) ('a' <= (c) && (c) <= 'z') #define isA(c) ('A' <= (c) && (c) <= 'Z') #define mem(a, b) memset(a, b, sizeof a); #define N 500050 #define M 2000005 #define llm 9223372036854775807 #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define PI acos(-1) #define endl "\n" #define bug cout << endl << " .....here!...." << endl; using namespace std; const int maxk=20;//(int)(log(Maxn)/log(2)+1);//最大跳跃层数，即log2(MaxN) struct Edge { int to,next,w; }edge[M*2]; int head[N],cnt; void add(int a,int b) {