lca(倍增)

例题:https://acm.hdu.edu.cn/showproblem.php?pid=2586

点击查看代码

#include <bits/stdc++.h>using namespace std;const int N = 40010;vector<int> v[N];
vector<int> w[N];int fa[N][31],cost[N][31],dep[N];
int n,m;
int a,b,c;void dfs(int root, int fno){fa[root][0] = fno;dep[root] = dep[fa[root][0]] + 1;for(int i = 1; i < 31; i ++){fa[root][i] = fa[fa[root][i - 1]][i - 1];cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];}int sz = v[root].size();for(int i = 0; i < sz; i ++){if(v[root][i] == fno)continue;cost[v[root][i]][0] = w[root][i];dfs(v[root][i],root);}
}int lca(int x,int y){//令 y 比 x 深if(dep[x] > dep[y])swap(x,y);int tmp = dep[y] - dep[x];int ans = 0;for(int j = 0; tmp; j ++, tmp >>= 1){if(tmp & 1) ans += cost[y][j],y = fa[y][j];}if(x == y) return ans;for(int j = 30; j >=0 && y != x; j --){if(fa[x][j] != fa[y][j]){ans += cost[x][j] + cost[y][j];x = fa[x][j];y = fa[y][j];}}//x和y都在lca(x,y)前一步了ans += cost[x][0] + cost[y][0];return ans;
}void solve(){memset(fa,0,sizeof(fa));memset(cost,0,sizeof(cost));memset(dep,0,sizeof(dep));cin >> n >> m;for(int i = 1; i <= n; i ++){v[i].clear();w[i].clear();}for(int i = 1; i <= n - 1; i ++){cin >> a >> b >> c;v[a].push_back(b);v[b].push_back(a);w[a].push_back(c);w[b].push_back(c);}dfs(1,0);for(int i = 0; i < m; i ++){cin >> a >> b;cout << lca(a,b) << '\n';}
}int main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}