1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| struct Graph{
static const int maxn=1e5+5, maxm=3e5+5;
struct star{int v,nex;}edge[maxm<<1];
int head[maxn],cnt;
void ini(int n){
for(int i=0;i<=n;i++) head[i]=-1;
cnt=-1;
}
void add_edge(int u,int v){
edge[++cnt]=star{v,head[u]};
head[u]=cnt;
edge[++cnt]=star{u,head[v]};
head[v]=cnt;
}
};
struct Lca:Graph{
int dep[maxn],dad[maxn],siz[maxn],son[maxn],chain[maxn],dfn[maxn];
void dfs1(int u,int father){
dep[u]=dep[father]+1;
dad[u]=father;
siz[u]=1;
son[u]=-1;
for(int i=head[u];~i;i=edge[i].nex){
int v=edge[i].v;
if(v==father)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int s,int&step){
dfn[u]=++step;
chain[u]=s;
if(son[u]!=-1) dfs2(son[u],s,step);
for(int i=head[u];~i;i=edge[i].nex){
int v=edge[i].v;
if(v!=son[u]&&v!=dad[u]) dfs2(v,v,step);
}
}
int lca(int x,int y){
while(chain[x]!=chain[y]){
if(dep[chain[x]]<dep[chain[y]]) swap(x,y);
x=dad[chain[x]];
}
return dep[x]<dep[y]?x:y;
}
}tree;
|
