第十三届蓝桥杯C++B组国赛H题——机房 (AC)

痛定思痛。 2023-09-28 23:19 33阅读 0赞

#### 目录 ####

*  1.机房
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例说明
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.Ac\_code
 *   *  tarjan
     *  倍增LCA

## 1.机房 ##

### 1.问题描述 ###

这天, 小明在机房学习。

他发现机房里一共有  n n n 台电脑, 编号为 1 到  n n n, 电脑和电脑之间有网线连 接, 一共有  n − 1 n-1 n−1 根网线将  n n n 台电脑连接起来使得任意两台电脑都直接或者间 接地相连。

小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和 多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑 用网线直接连接了另外  d d d 台电脑, 那么任何经过这台电脑的信息都会延迟  d d d 单 位时间 (发送方和接收方也会产生这样的延迟, 当然如果发送方和接收方都是 同一台电脑就只会产生一次延迟)。

小明一共产生了  m m m 个疑问: 如果电脑  u i u\_\{i\} ui 向电脑  v i v\_\{i\} vi 发送信息, 那么信息从  u i u\_\{i\} ui 传到  v i v\_\{i\} vi 的最短时间是多少?

### 2.输入格式 ###

输入共  n + m n+m n\+m 行, 第一行为两个正整数  n , m n,m n,m 。

后面  n − 1 n−1 n−1 行, 每行两个正整数  x , y x, y x,y 表示编号为  x x x 和  y y y 的两台电脑用网线 直接相连。

后面  m m m 行, 每行两个正整数  u i , v i u\_\{i\}, v\_\{i\} ui,vi表示小明的第  i i i 个疑问。

### 3.输出格式 ###

输出共  m m m 行, 第  i i i 行一个正整数表示小明第  i i i 个疑问的答案。

### 4.样例输入 ###

4 3  
1 2  
1 3  
2 4  
2 3  
3 4  
3 3

### 5.样例说明 ###

这四台电脑各自的延迟分别为 2,2,1,1。

对于第一个询问, 从 2 到 3 需要经过 2,1,3, 所以时间和为 2+2+1=5 。

对于第二个询问, 从 3 到 4 需要经过 3,1,2,4, 所以时间和为 1+2+2+1=6。

对于第三个询问, 从 3 到 3 只会产生一次延迟, 所以时间为 1 。

### 6.数据范围 ###

n , m ≤ 100000 n,m≤100000 n,m≤100000

### 7.原题链接 ###

[机房][Link 1]

## 2.解题思路 ##

还是一道比较明显的求`LCA`(最近公共祖先)模型的题目,我们可以使用多种方法来解决该问题，这里我们使用更好写的离线的`tarjan`算法来解决该问题 (**已补充倍增做法**)。

除去`tarjan`算法必用的基础数组，我们还有一个数组`d[]`,`d[i]`记录的是每个点的出度，也就是它的延迟时间，以及数组`w[]`,`w[i]`的含义是点`i`到根节点的延迟时间。在通过`dfs`求出每个点`i`的`w[i]`以后，在`tarjan`中我们该如何求出两点的延迟时间呢？

我们设点`i`到`j`的延迟时间为 f ( i , j ) f(i,j) f(i,j),当我们求得`i`与`j`的最近公共祖先为`anc`，我们首先让 f ( i , j ) = w \[ i \] + w \[ j \] f(i,j)=w\[i\]+w\[j\] f(i,j)=w\[i\]\+w\[j\],但很明显，我们多加了两遍 w \[ a n c \] w\[anc\] w\[anc\]，所以我们需要减去两倍的 w \[ a n c \] w\[anc\] w\[anc\]，但延迟时间还包括经过`anc`的时间，所以还得加上一个 d \[ a n c \] d\[anc\] d\[anc\]。**此处请结合`w[]`和`d[]`的含义理解。**  
最后能得出式子: f ( i , j ) = w \[ i \] + w \[ h \] − w \[ a n c \] ∗ 2 + d \[ a n c \] f(i,j)=w\[i\]+w\[h\]-w\[anc\]\*2+d\[anc\] f(i,j)=w\[i\]\+w\[h\]−w\[anc\]∗2\+d\[anc\]![在这里插入图片描述][462bb348858a4b6ca204104d32bbbe5f.png]

>  假设图中当求`D`到`E`的延迟时间，根据数组定义我们可知  w \[ D \] w\[D\] w\[D\] 为 \[ A , B , C , D \] \[A,B,C,D\] \[A,B,C,D\]四点的延迟时间之和。 w \[ E \] w\[E\] w\[E\]为 \[ E , B , A \] \[E,B,A\] \[E,B,A\]三点延迟之和。从`D`到`E`点所求应该是 \[ D , C , B , E \] \[D,C,B,E\] \[D,C,B,E\]四点之和。`D`和`E`的最近公共祖先为`B`,可以看出对于从`B`点开始一直到根节点这一段我们是不需要的，也就是 w \[ B \] w\[B\] w\[B\]被多加了两遍，所以我们应该减去 w \[ B \] ∗ 2 w\[B\]\*2 w\[B\]∗2。但最后答案 B B B点本身是应该计算进来的，所以我们单独加进来。其中 l c a ( D , E ) lca(D,E) lca(D,E)即为 B B B，可得式子:  
>  f ( d , e ) = w \[ D \] + W \[ E \] − w \[ l c a ( D , E ) \] ∗ 2 + d \[ l c a ( D , E ) \] f(d,e)=w\[D\]+W\[E\]-w\[lca(D,E)\]\*2+d\[lca(D,E)\] f(d,e)=w\[D\]\+W\[E\]−w\[lca(D,E)\]∗2\+d\[lca(D,E)\]

我们利用这个式子在`tarjan`函数中就能得出每个询问的答案，当然对于起始和结束都在同一个节点的情况下,它的答案就是当前节点的出度，我们可以进行特判一下。输入输出较多，建议使用`scanf`和`printf`进行输入输出。

**时间复杂度**:`dfs`：每个点遍历一次,复杂度级别 O ( n ) O(n) O(n),`tarjan`算法复杂度接近  O ( n + m ) O(n+m) O(n\+m)

## 3.Ac\_code ##

### tarjan ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef pair<int,int> PII;
    const int N=100010;
    
    unordered_map<int,vector<int>> gra;
    int n,m;
    //单个点的出度
    int d[N];
    //记录点i到根节点的延迟
    int w[N];
    //并查集数组
    int q[N];
    //记录答案
    int res[N];
    int st[N];
    //存下查询
    vector<PII>	query[N];
    //并查集查询
    int find(int x){
        
    	if(x!=q[x]) q[x]=find(q[x]);
    	return q[x];
    }
    
    void dfs(int u,int fa)
    {
        
    	w[u]+=d[u];
    	for(auto g:gra[u]){
        
    		if(g==fa) continue;
    		w[g]+=w[u];
    		dfs(g,u);
    	}
    }
    
    void tarjan(int u)
    {
        
    	st[u]=1;
    	for(auto j:gra[u]){
        
    		if(!st[j])
    		{
        
    			tarjan(j);
    			q[j]=u;
    		}
    	}
    	for(auto item: query[u]){
        
    		int y=item.first,id=item.second;
    		if(st[y]==2){
        
    			int anc=find(y);
    			res[id]=w[y]+w[u]-w[anc]*2+d[anc];
    		}
    	}
    	st[u]=2;
    }
    int main() 
    {
        
    	cin>>n>>m;
    	for(int i=0;i<n-1;++i){
        
    		int a,b;
    		scanf("%d%d",&a,&b);
    		gra[a].push_back(b);
    		gra[b].push_back(a);
    		d[a]++,d[b]++;
    	}
    	for(int i=0;i<m;++i){
        
    		int a,b;
    		scanf("%d%d",&a,&b);
    		if(a!=b){
        
    			query[a].push_back({
        b,i});
    			query[b].push_back({
        a,i});
    		}else{
        
    			res[i]=d[a];
    		}
    	}
    	dfs(1,-1);
    	for(int i=1;i<=n;++i) q[i]=i;
    	tarjan(1);
    	for(int i=0;i<m;++i) printf("%d\n",res[i]);
        return 0;
    }

### 倍增LCA ###

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    const int N = 200010;
    
    std::vector<int> e[N];
    int n, m;
    int depth[N], fa[N][30];
    int root;
    int w[N], d[N];
    void bfs(int root)
    {
        
    	memset(depth, 0x3f, sizeof depth);
    	depth[0] = 0, depth[root] = 1;
    	queue<int> q;
    	q.push(root);
    	while (!q.empty()) {
        
    		auto t = q.front();
    		q.pop();
    		for (auto j : e[t]) {
        
    			if (depth[j] > depth[t] + 1) {
        
    				depth[j] = depth[t] + 1;
    				q.push(j);
    				fa[j][0] = t;
    				for (int k = 1; k <= 15; k++) {
        
    					fa[j][k] = fa[fa[j][k - 1]][k - 1];
    				}
    			}
    		}
    	}
    }
    
    int lca(int a, int b) {
        
    	if (depth[a] < depth[b]) swap(a, b);
    	for (int k = 20; k >= 0; k--) {
        
    		if (depth[fa[a][k]] >= depth[b]) {
        
    			a = fa[a][k];
    		}
    	}
    	if (a == b) return a;
    	for (int k = 20; k >= 0; --k) {
        
    		if (fa[a][k] != fa[b][k]) {
        
    			a = fa[a][k];
    			b = fa[b][k];
    		}
    	}
    	return fa[a][0];
    }
    void dfs(int u, int fa)
    {
        
    	w[u] += d[u];
    	for (auto g : e[u]) {
        
    		if (g == fa) continue;
    		w[g] += w[u];
    		dfs(g, u);
    	}
    }
    void solve()
    {
        
    	cin >> n >> m;
    	for (int i = 0; i < n - 1; ++i) {
        
    		int a, b;
    		cin >> a >> b;
    		e[a].push_back(b);
    		e[b].push_back(a);
    		d[a]++, d[b]++;
    	}
    	dfs(1, -1);
    	bfs(1);
    	for (int i = 0; i < m; ++i)
    	{
        
    		int a, b;
    		cin >> a >> b;
    		int c = lca(a, b);
    		cout << w[a] + w[b] - w[c] * 2 + d[c] << '\n';
    	}
    }
    int main()
    {
        
    	solve();
    	return 0;
    }

[Link 1]: https://www.lanqiao.cn/problems/2198/learning/
[462bb348858a4b6ca204104d32bbbe5f.png]: https://img-blog.csdnimg.cn/462bb348858a4b6ca204104d32bbbe5f.png