蓝桥杯2022年第十三届决赛真题-机房 - C语言网 (dotcpp.com)

题意：

一共有n个结点，n-1条边，因此这是棵树

信息经过一个结点，就会产生一定的延迟，具体延迟的时间等于该结点的度数

每次询问树上两个结点，问两个结点之间路径中所有点度数之和

思路：

树上前缀和+LCA

因为是棵树，对于树上任意两个结点，路径是唯一的

多次询问，如果每次询问都去暴力跑路径的话，复杂度将会是O(qn)，会超时

因此我们去求出每个结点离根节点的路径中所有结点的度数之和，相当于去预处理所有结点的前缀和

如下图，黑色的线就是x到根节点的路径，结点x的前缀和就是这条路径上所有结点度数之和

 

 黑色表示结点x前缀和

蓝色表示结点y前缀和

红色表示lca(x,y)前缀和

黄色表示lca(x,y)的父节点的前缀和

那么x到y的路径的结点的度数之和就是 in[x]+in[y]-in[lca(x,y)]-in[st[lca(x,y][0]]

其中in[x]表示结点x到根节点的路径中度数之和

那么我们如何去求每个结点离根节点的前缀和：

bfs或dfs去遍历所有结点，然后从父结点向子结点递推：

dep[u]=dep[st[u][0]]+1;

其中st[u][0]表示结点u的父结点

为了防止爆栈，用bfs比较合适

我们如何去求lca：

首先动态规划预处理st表

 然后对于树上任意两点x,y，先让x和y的深度相等

深度相等之后，让x和y以二进制拆分的倍增往上爬，直到爬到它们的最近公共祖先

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e5+10,mxe=1e5+10;
struct ty{int to,next;
}edge[mxe<<1];
queue<int> q;
int n,m,x,y,tot=0;
int in[mxn],head[mxn],st[mxn][25],dep[mxn];
void init(){tot=0;for(int i=0;i<=n;i++){head[i]=-1;in[i]=dep[i]=0;for(int j=0;j<mxn;j++) st[i][j]=0;}while(!q.empty()) q.pop();
}
void add(int u,int v){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void bfs(){q.push(1);while(!q.empty()){int u=q.front();q.pop();dep[u]=dep[st[u][0]]+1;in[u]+=in[st[u][0]];for(int i=head[u];~i;i=edge[i].next){if(edge[i].to==st[u][0]) continue;st[edge[i].to][0]=u;q.push(edge[i].to);}}
}
int lca(int u,int v){if(dep[u]<dep[v]) swap(u,v);for(int i=19;i>=0;i--){if(dep[st[u][i]]<dep[v]) continue;u=st[u][i];}if(u==v) return u;for(int i=19;i>=0;i--){if(st[u][i]!=st[v][i]){u=st[u][i];v=st[v][i];}}return st[u][0];
}
int main(){scanf("%d%d",&n,&m);memset(head,-1,sizeof(head));//init();for(int i=1;i<=n-1;i++){scanf("%d%d",&x,&y);add(x,y);in[y]++;add(y,x);in[x]++;}bfs();for(int len=1;len<20;len++){for(int i=1;i<=n;i++) st[i][len]=st[st[i][len-1]][len-1];}int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);int tmp=lca(x,y);printf("%d\n",in[x]+in[y]-in[tmp]-in[st[tmp][0]]);}return 0;
}