AcWing 1171. 距离
原题链接
中等
作者:
徐学神
,
2024-04-07 21:32:31
,
所有人可见
,
阅读 1
求赞!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+10;
vector<pair<ll,ll>> e[N];
ll n,m,d[N],s[N],f[20][N];
void dfs(ll u,ll fa) {
d[u]=d[fa]+1;
f[0][u]=fa;
for(ll p=1; p<=15; p++) f[p][u]=f[p-1][f[p-1][u]];
for(auto x:e[u]) {
if(x.first==fa) continue;
s[x.first]=s[u]+x.second;
dfs(x.first,u);
}
}
ll lca(ll x,ll y) {
if(d[x]<d[y]) swap(x,y);
ll stp=d[x]-d[y];
for(ll i=log2(stp); i>=0; i--) if(stp>>i&1) x=f[i][x];
if(x==y) return x;
for(ll i=15; i>=0; i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
return f[0][x];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(ll i=1; i<n; i++) {
ll x,y,k;
cin>>x>>y>>k;
e[x].push_back({y,k});
e[y].push_back({x,k});
}
dfs(1,0);
while(m--) {
ll x,y;
cin>>x>>y;
cout<<s[x]+s[y]-2*s[lca(x,y)]<<"\n";
}
return 0;
}