悬关，到底哪里没加半角空格啊

# P13081 题解 

特别鸣谢：Deepseek 撰写了本文样例解释部分，并润色了本文部分描述。

管理员在打回的时候能不能指出我到底哪里错了，比如举个**文中的错误例子**，**麻烦您了**！

## 闲话

话说为啥我在本地运行会 RE，但是交上去就能 A？

## 题目大意

题目给出一个树形结构的新加坡地图，有 $V$ 个节点和 $V-1$ 条边。我们需要处理 $Q$ 次查询，每次查询给出 $5$ 个不同的赞助商位置，要求计算在这些赞助商两两之间路径上的所有边的广告投放成本总和。

## 解题思路 

首先，在树里面，任意两点之间有且仅有一条路径。这意味着两点间的最短路径就是唯一的路径。

如果我们需要找到覆盖所有赞助商两两之间路径的边集，就相当于找到包含所有赞助商的“最小连通子树”（能这么说吧）的边。

然后我们考虑使用 LCA 计算两点间路径长度。

那么我们该如何实现呢？我们可以一个一个地添加赞助商位置，并计算新增的最小边权和。

## 代码详解 

### 预处理部分 

```cpp 
int n,q,dep[N],fa[N][25],len[N],a[7];
struct edge{
    int v,w;
};
vector<edge> e[N];
```

- $dep$：存储每个节点的深度。 
- $fa$：倍增法求 LCA 的父节点数组，$fa_{u,i}$ 表示u节点的第 $2^i$ 级祖先。 
- $len$：存储从根节点到每个节点的路径总长度。 
- $e$：vector 邻接表。

### 计算路径长度函数 

```cpp 
int dis(int u,int v,int lca){
    return len[u]+len[v]-2*len[lca];
}
```

计算 u 和 v 两点间路径长度，通过它们的 LCA 作为中转站来计算。

### 预处理路径长度 

```cpp 
void glen(int u,int f){
	for(edge ed:e[u]){
		int v=ed.v;
		if(v==f) continue;
		len[v]=len[u]+ed.w;
		glen(v,u);
	}
}
```

DFS 计算从根节点到每个节点的路径总长度。

### LCA 模版 

```cpp 
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;i<=22;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(edge ed:e[u]){
		if(ed.v!=f) dfs(ed.v,u);
	}
}

int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=22;i>=0;i--){
		if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
	}
	if(u==v) return v;
	for(int i=22;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}
```

### 主函数关键部分

```cpp 
while(q--){
	int old,ans=0,now;
	for(int i=1;i<=5;i++){
		scanf("%d",&a[i]);
		a[i]++;
	}
	old=lca(a[1],a[2]);
	ans+=dis(a[1],a[2],old);
	for(int i=3;i<=5;i++){
		now=lca(old,a[i]);
		if(now!=old) ans+=dis(old,a[i],now);
		else{
			int mn=INT_MAX;
			for(int j=1;j<i;j++){
				int tmp=lca(a[j],a[i]);
				mn=min(mn,dis(tmp,a[i],tmp));
			}
			ans+=mn;
		}
		old=now;
	}
	printf("%d\n",ans);
}
```

1. 读取 $5$ 个赞助商位置。 
2. 每次初始计算前两个赞助商之间的路径成本。 
3. 逐个添加剩余赞助商：
- 如果新赞助商不在当前连通子树中，添加连接路径。 
- 如果已在当前子树中，找到到已有赞助商的最短路径。 

## 示例解析 

[Mermaid 使用网址（把下文中的 Mermaid 部分复制进这个网址即可食用）。](https://www.processon.com/mermaid?utm_source=biying&utm_medium=semmermaid&utm_term=mermaid&utm_content=&uc_pagenum={pagenum}&uc_adposition=&msclkid=fb7ec36e42631c414745ab9d66fd8c11)

### 样例 1 解析 

#### 输入：
```
5 
0 1 1 
1 2 2 
2 3 3 
3 4 4 
1 
4 0 3 1 2 
```

#### 树结构：
```mermaid 
graph TD 
0 ---|1| 1 
1 ---|2| 2 
2 ---|3| 3 
3 ---|4| 4 
```

赞助商位置：$4,0,3,1,2$ 

1. 初始计算4和0之间的路径：$4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 0$，成本为 $10$。 
2. 其他赞助商都在这个路径上，不需要额外边。 
3. 总成本：$10$。

### 样例 2 第一次查询解析 

#### 输入：
```
6 
4 0 4 
0 1 2 
1 3 9 
3 5 1 
3 2 5 
2 
4 0 3 5 2 
```

#### 树结构：
```mermaid 
graph TD 
4 ---|4| 0 
0 ---|2| 1 
1 ---|9| 3 
3 ---|1| 5 
3 ---|5| 2 
```

赞助商位置：$4,0,3,5,2$。 

1. 初始计算 $4$ 和 $0$ 之间的路径：$4 \rightarrow 0$，成本 $4$。 
2. 添加 $3$：
- $\operatorname{LCA}(0,3)=1$。 
- 路径 $0 \rightarrow 1 \rightarrow 3$，成本 $2+9=11$。 
- 总成本 $4+11=15$。 
3. 添加 $5$：
- $5$ 在 $1 \rightarrow 3 \rightarrow 5$ 路径上。 
- 最短新增路径是 $3 \rightarrow 5$，成本 $1$。  
- 总成本 $15+1=16$。 
4. 添加 $2$：
- $2$ 在 $1 \rightarrow 3 \rightarrow 2$ 路径上。 
- 最短新增路径是 $3 \rightarrow 2$，成本 $5$。 
- 总成本 $16+5=21$。 

### 样例 2 第二次查询解析 

赞助商位置：$0,4,1,3,5$。 

1. 初始计算 $0$ 和 $4$ 之间的路径：$0 \rightarrow 4$，成本 $4$。 
2. 添加 $1$：
- $\operatorname{LCA}(4,1)=0$。 
- 路径 $0 \rightarrow 1$，成本 $2$。 
- 总成本 $4+2=6$。 
3. 添加 $3$：
- $\operatorname{LCA}(0,3)=1$。 
- 路径 $1 \rightarrow 3$，成本 $9$。 
- 总成本 $6+9=15$。 
4. 添加 $5$：
- $5$ 在 $1 \rightarrow 3 \rightarrow 5$ 路径上。 
- 最短新增路径是 $3 \rightarrow 5$，成本 $1$。 
- 总成本 $15+1=16$。 

注意：边 $3 \rightarrow 2$ 没有被包含在任何路径中，因此不需要计算其成本。

## 复杂度分析 

1. 预处理：
- DFS 遍历树：$O(V)$。
- 倍增法预处理：$O(V \operatorname{log} V)$。
2. 每次查询：
- 计算 $5$ 个点的 LCA 和路径长度：$O(\operatorname{log} V)$。
- 总查询复杂度：$O(Q \operatorname{log} V)$。


## 完整 AC 代码

```cpp
#include<bits/stdc++.h>
#define N 50005
//#define int long long
using namespace std;

int n,q,dep[N],fa[N][25],len[N],a[7];
struct edge{
	int v,w;
};
vector<edge> e[N];

int dis(int u,int v,int lca){
	return len[u]+len[v]-2*len[lca];
}
void glen(int u,int f){
//	cout<<u<<","<<f<<endl;
	for(edge ed:e[u]){
		int v=ed.v;
		if(v==f) continue;
		len[v]=len[u]+ed.w;
		glen(v,u);
	}
}
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;i<=22;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(edge ed:e[u]){
		if(ed.v!=f) dfs(ed.v,u);
	}
}
int lca(int u,int v){
//	cout<<1;
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=22;i>=0;i--){
		if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
	}
	if(u==v) return v;
	for(int i=22;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}

signed main()
{
//	freopen("Advertisements.in","r",stdin);
//	freopen("Advertisements.out","w",stdout);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		u++;
		v++;
		e[u].push_back(edge{v,w});
		e[v].push_back(edge{u,w});
	}
	glen(1,0);
	dfs(1,0);
	cin>>q;
	while(q--){
		int old,ans=0,now;
		for(int i=1;i<=5;i++){
			scanf("%d",&a[i]);
			a[i]++;
		}
		old=lca(a[1],a[2]);
		ans+=dis(a[1],a[2],old);
		for(int i=3;i<=5;i++){
			now=lca(old,a[i]);
			if(now!=old) ans+=dis(old,a[i],now);
			else{
				int mn=INT_MAX;
				for(int j=1;j<i;j++){
					int tmp=lca(a[j],a[i]);
					mn=min(mn,dis(tmp,a[i],tmp));
				}
				ans+=mn;
			}
			old=now;
		}
		printf("%d\n",ans);
	}
	return 0;
}
```

**完结撒花！**