1.机房

1.问题描述

这天, 小明在机房学习。

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

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

小明一共产生了 $m$ 个疑问: 如果电脑 $u_i$ 向电脑 $v_i$ 发送信息, 那么信息从 $u_i$ 传到 $v_i$ 的最短时间是多少?

2.输入格式

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

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

后面 $m$ 行, 每行两个正整数 $u_i,v_i$表示小明的第 $i$ 个疑问。

3.输出格式

输出共 $m$ 行, 第 $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\le 100000$

7.原题链接

机房

2.解题思路

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

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

我们设点i到j的延迟时间为$f(i,j)$,当我们求得i与j的最近公共祖先为anc，我们首先让$f(i,j)=w[i]+w[j]$,但很明显，我们多加了两遍$w[anc]$，所以我们需要减去两倍的$w[anc]$，但延迟时间还包括经过anc的时间，所以还得加上一个$d[anc]$。此处请结合w[]和d[]的含义理解。
最后能得出式子:$$f(i,j)=w[i]+w[h]-w[anc]\ast 2+d[anc]$$

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

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

时间复杂度:dfs：每个点遍历一次,复杂度级别$O(n)$,tarjan算法复杂度接近 $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;
}