最近公共祖先LCA

LCA模板

vector<int> adj[N];
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	par[u][0]=fa;
	for(int i=1;i<=log2(dep[u]);i++)par[u][i]=par[par[u][i-1]][i-1];
	for(auto v:adj[u]){
		if(v==fa)continue;
		dfs(v,u);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	while(dep[u]>dep[v]){
		u=par[u][(int)log2(dep[u]-dep[v])];
	}
	if(u==v)return u;
	for(int i=log2(dep[u]);i>=0;i--){
		if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
	}
	return par[u][0];
}

三个点到一个点的最小花费最小

• 三个点的lca必有两个相同
• 两个相同，那么就是另一个点
• 三个相同，就是当前点 证明第二点：

    .
    / \
   /   \
  / \   \
   /   \   c
  a     b
  

  将上述点拉直

  c  
   |
   |
   |
   |
  / \   
   /   \   
  a     b
  

  假设有CW存在一点H比W更优
  H点：CH+(AW+WH)+(BW+WH)=CW+AW+BW+WH>=CW+AW+BW所以W为最优点

   c  
   |
   |
   h
   |
   w
  / \   
   /   \   
  a     b
  

  距离为：dep[a]+dep[b]+dep[c]-dep[lca(a,b)]-dep[lca(a,c)]-dep[lca(b,c)]