分析
是一道lca题目，可以直接套模板 + 前缀和处理点权
具体思路：
1.n台电脑用n-1条网线相连，任意两个节点之间有且仅有一条路径（拆分成各自到公共祖先节点的路径——lca）；
2.“延迟时间”：看成是节点点权（要求一条链上某个区间的值——前缀和）
——用sum[]存储根节点到 i 节点的点权和
LCA
三种求法：
（1）朴素求法：
先将两点位于同一深度，然后同时向上跳；一次查询：O(n^2)
（2）倍增求法：
朴素求法的改进版（朴素是一步一步跳，倍增是用f[][]优化，每次向上都是以其父节点为目标）
（3）Tarjan（留一下，还没学~）
倍增求法的步骤：
1.存图/树
2.dfs(int x,int father)更新f[][]（表示节点 i 的第2^j个祖先节点）、d[]（深度）
（1）更新d[x]和f[x][0]
（2）for(1~20)更新f[x][i]
（3）for(遍历邻接点)递归dfs()
3.lca
（1）先将两点跳到同一深度（深度大的往上跳）
（2）若相等，则该点就是lca；若不相等，则从大到小，如果f[][]不等，则更新两点，lca=f[x][0]
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int head[N],d[N],f[N][30],a[N],sum[N],cnt,n,m;
struct edges{
int to;
int ne;
}e[N*2];//存两条边记得数组开成2倍
//初始化别忘了（容易忘建议直接写main中）
void init()
{
memset(head,-1,sizeof head);
}
//链式前向星存边
void addedge(int u,int v)
{
e[cnt].to = v;
e[cnt].ne = head[u];
head[u] = cnt ++;
}
//dfs处理d[]、f[][]、sum[]
void dfs(int x,int father)
{
d[x] = d[father] + 1;
f[x][0] = father;
sum[x] = sum[f[x][0]] + a[x]; //lca模板多了这一步~
for(int i = 1;i <= 20;i ++)
{
f[x][i] = f[f[x][i-1]][i-1];
}
for(int i = head[x];i != -1;i = e[i].ne)
{
int j = e[i].to;
if(j == father) continue; //加的是双向边，所以邻接点有其父节点，遍历时跳过
dfs(j,x); //递归遍历
}
return ;
}
//lca找到最近公共祖先节点
int lca(int u,int v)
{
if(d[u] < d[v]) swap(u,v);
for(int i = 20;i >= 0;i --)
{
if(d[f[u][i]] >= d[v]) u = f[u][i];
}
if(u == v)
{
return u;
}
for(int i = 20;i >= 0;i --)
{
if(f[u][i] != f[v][i])
{
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
int main()
{
init();
scanf("%d %d",&n,&m);
for(int i = 0;i < n - 1;i ++)
{
int u,v;
scanf("%d %d",&u,&v);
a[u] ++,a[v] ++;
addedge(u,v),addedge(v,u);
}
dfs(1,0);
while(m --)
{
int u,v;
scanf("%d %d",&u,&v);
int mid = lca(u,v);
int ans = sum[u] + sum[v] - 2 * sum[mid] + a[mid]; //两点之间的权值和
printf("%d\n",ans);
}
return 0;
}