Editorial for dynamic LCA
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của ladpro98
#include <vector> #include <iostream> #include <cstdio> #include <cmath> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define SZ(a) (int((a).size())) #define PB push_back #define VI vector<int> const int N = 100005; using namespace std; VI a[N]; int p[N][20], d[N]; int n, m, lg; void DFS(int u) { FOR(i, 0, SZ(a[u])) { int v = a[u][i]; if (v != p[u][0]) { p[v][0] = u; d[v] = d[u] + 1; DFS(v); } } } int lca(int u, int v) { if (d[u] > d[v]) swap(u, v); REPD(i, lg, 0) if (d[v] - d[u] >= (1 << i)) v = p[v][i]; if (u == v) return u; REPD(i, lg, 0) if (p[u][i] != p[v][i]) {u = p[u][i]; v = p[v][i];} return p[u][0]; } int main() { ios :: sync_with_stdio(0); cin.tie(0); while (cin >> n) { if (n == 0) break; REP(i, 1, n) a[i].clear(); int u, v, root = 1; char ch; FOR(i, 1, n) { cin >> u >> v; a[u].PB(v); a[v].PB(u); } DFS(1); lg = log2(n) + 1; FOR(j, 1, lg) REP(i, 1, n) p[i][j] = p[p[i][j - 1]][j - 1]; cin >> m; while (m--) { cin >> ch; if (ch == '!') cin >> root; else { cin >> u >> v; int ur = lca(u, root); int vr = lca(v, root); int uv = lca(u, v); if (ur == vr) cout << uv << '\n'; else if (ur == uv) cout << vr << '\n'; else cout << ur << '\n'; } } } return 0; }
Code mẫu của hieult
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define Fit(i,c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++) #define inf 1000000005 #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) #define mod 1000000007 #define sz(a) ((int)(a).size()) template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return __builtin_popcountll(s);} #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) typedef unsigned long long ull; typedef long long ll; typedef double ld; #define eps 1e-9 typedef pair<int, int> II; template<class T> T gcd(T a, T b){ T r; while (b != 0) { r = a % b; a = b; b = r; } return a;} template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } #define PI 2 * acos(0) #define maxn 200005 int n, q, deep[maxn], dad[maxn][20]; vector<int> V[maxn]; void go(int par, int u){ deep[u] = deep[par] + 1; dad[u][0] = par; Rep(i, sz(V[u])){ int v = V[u][i]; if(v == par) continue; go(u, v); } } int lca(int u, int v){ if(deep[u] > deep[v]) swap(u, v); for(int i = 18; i >= 0; i--){ if(deep[v] - deep[u] >= (1 << i)) v = dad[v][i]; } for(int i = 18; i >= 0; i--){ if(dad[u][i] != dad[v][i]){ u = dad[u][i]; v = dad[v][i]; } } if(u != v) u = dad[u][0]; return u; } int main() { // freopen("dynamic.in", "r", stdin); // freopen("dynamic.out", "w", stdout); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); while(cin >> n){ if(n == 0) break; For(i, 1, n) V[i].clear(); int u, v; Rep(run, n - 1){ cin >> u >> v; V[u].pb(v); V[v].pb(u); } ms(dad, 0); ms(deep, 0); go(0, 1); for(int i = 1; i <= 18; i++) for(int j = 1; j <= n; j++){ dad[j][i] = dad[dad[j][i - 1]][i - 1]; } cin >> q; int root = 1; char ch; Rep(iq, q){ cin >> ch >> u; if(ch == '!'){ root = u; } else{ cin >> v; int tu = lca(root, u), tv = lca(root, v); int res = (deep[tu] >= deep[tv] ? tu : tv); int tuv = lca(u, v); res = (deep[res] >= deep[tuv] ? res : tuv); cout << res << "\n"; } } } return 0; }
Comments