论本题数据都卡了什么算法
原题链接：60053.最短路
2025-07-22 12:46:23
发布于：湖南
40阅读
0回复
0点赞
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int> v[500005];
int dep[500005], father[500005];
bool vis[500005];
int n, m;
void dfs(int cur, int fa){
dep[cur] = dep[fa] + 1;
father[cur] = fa;
for(int i:v[cur]){
if(i == fa) continue;
dfs(i, cur);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
while(m--){
int tmp;
cin >> tmp;
if(tmp == 1){
int idx;
cin >> idx;
vis[idx] = 1;
}else{
int x, y;
cin >> x >> y;
if(dep[x] > dep[y]) swap(x, y);
int ans = 0, ct = 0;
while(dep[y] > dep[x]) y = father[y], ans++, ct += vis[y];
while(x != y){
x = father[x], y = father[y];
ans += 2;
if(x == y) ct += vis[x];
else ct += vis[x] + vis[y];
}
cout << ans - ct << '\n';
}
}
return 0;
}
有帮助，赞一个