Editorial for VO 15 Bài 1 - Cây
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.
Dạng: LCA, cấu trúc dữ liệu
Yêu cầu: Cho cây ~N~ đỉnh. Truy vấn ~u~, ~v~, tìm ~LCA(u~, ~u + 1~, ~u + 2~, ~\dots~, ~v)~
Cách làm:
~LCA(u~, ~u + 1~, ~u + 2~, ~\dots~, ~v)~ ~=~ ~LCA(LCA(u~, ~u + 1~, ~\dots~, ~k~ - ~1)~, ~LCA(k~, ~k + 1~, ~\dots~, ~v))~
Vì thế bài này có thể áp dụng cấu trúc dữ liệu như IT hoặc RMQ kết hợp LCA để giải.
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 <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #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 FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 100005; using namespace std; VI a[N]; int par[N][20], ans[N][20], d[N]; int n, q, lg; void dfs(int u) { TR(v, a[u]) if (*v != par[u][0]) { par[*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 = par[v][i]; if (u == v) return u; REPD(i, lg, 0) if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } return par[u][0]; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> q; int u, v; FOR(i, 1, n) { cin >> u >> v; a[u].PB(v); a[v].PB(u); } dfs(1); lg = log2(n) + 2; REP(j, 1, lg) REP(i, 1, n) par[i][j] = par[par[i][j - 1]][j - 1]; REP(i, 1, n) ans[i][0] = i; REP(j, 1, lg) for(int i = 1; i + (1 << j - 1) <= n; i++) ans[i][j] = lca(ans[i][j - 1], ans[i + (1 << j - 1)][j - 1]); int i, j; while (q--) { cin >> i >> j; int k = log2(j - i + 1); cout << lca(ans[i][k], ans[j - (1 << k) + 1][k]) << '\n'; } return 0; }
Code mẫu của RR
#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } #define sqr(x) ((x) * (x)) using namespace std; const int MN = 70111; int n, q, h[MN]; vector<int> ke[MN]; int father[22][MN], ln[MN], res[22][MN]; void dfs(int u, int fu) { REP(i,ke[u].size()) { int v = ke[u][i]; if (v == fu) continue; h[v] = h[u] + 1; father[0][v] = u; dfs(v, u); } } void init() { for(int i = 1, res = 0; i < MN; i *= 2, ++res) ln[i] = res; FOR(i,2,MN-1) if (!ln[i]) ln[i] = ln[i-1]; // PR(ln, 10); FOR(lg,1,20) FOR(i,1,n) father[lg][i] = father[lg-1][father[lg-1][i]]; } int lca(int u, int v) { if (u == v) return u; if (h[u] > h[v]) swap(u, v); if (h[u] < h[v]) { FORD(lg,20,0) { int x = father[lg][v]; if (h[x] >= h[u]) { v = x; } } } if (u == v) return u; FORD(lg,20,0) if (father[lg][u] != father[lg][v]) { u = father[lg][u]; v = father[lg][v]; } return father[0][u]; } #define TWO(X) (1<<(X)) int main() { ios :: sync_with_stdio(false); while (cin >> n >> q) { FOR(i,1,n) ke[i].clear(); FOR(i,2,n) { int u, v; cin >> u >> v; ke[u].push_back(v); ke[v].push_back(u); } h[1] = 1; dfs(1, -1); init(); FOR(i,1,n) res[0][i] = i; FOR(lg,1,20) FOR(i,1,n-TWO(lg)+1) res[lg][i] = lca(res[lg-1][i], res[lg-1][i+TWO(lg-1)]); while (q--) { int u, v; cin >> u >> v; int len = v - u + 1; int lg = ln[len]; cout << lca(res[lg][u], res[lg][v - TWO(lg) + 1]) << "\n"; } } }
Code mẫu của skyvn97
#include<cstdio> #include<vector> #define MAX 100100 #define LOG 17 #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) #define MASK(i) (1<<(i)) using namespace std; vector<int> g[MAX]; int minLab[MAX][LOG+1],maxLab[MAX][LOG+1],lg2[MAX]; int par[MAX][LOG+1],h[MAX],lab[MAX]; int n,q,cnt; void loadtree(void) { scanf("%d%d",&n,&q); REP(zz,n-1) { int u,v; scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } h[0]=-1; } void dfs(int u) { lab[u]=++cnt; REP(i,g[u].size()) if (g[u][i]!=par[u][0]) { int v=g[u][i]; par[v][0]=u; h[v]=h[u]+1; dfs(v); } } int minLabel(int u,int v) { return (lab[u]<lab[v]?u:v); } int maxLabel(int u,int v) { return (lab[u]>lab[v]?u:v); } void prepare(void) { dfs(1); FOR(i,1,n) minLab[i][0]=maxLab[i][0]=i; FOR(j,1,LOG) { FOR(i,1,n) par[i][j]=par[par[i][j-1]][j-1]; FOR(i,1,n-MASK(j)+1) { minLab[i][j]=minLabel(minLab[i][j-1],minLab[i+MASK(j-1)][j-1]); maxLab[i][j]=maxLabel(maxLab[i][j-1],maxLab[i+MASK(j-1)][j-1]); } } FOR(i,1,n) { while (MASK(lg2[i])<=i) lg2[i]++; lg2[i]--; } } int getMinLabel(int l,int r) { int k=lg2[r-l+1]; return (minLabel(minLab[l][k],minLab[r-MASK(k)+1][k])); } int getMaxLabel(int l,int r) { int k=lg2[r-l+1]; return (maxLabel(maxLab[l][k],maxLab[r-MASK(k)+1][k])); } int LCA(int u,int v) { if (h[u]<h[v]) return (LCA(v,u)); FORD(i,LOG,0) if (h[par[u][i]]>=h[v]) u=par[u][i]; if (u==v) return (v); FORD(i,LOG,0) if (par[u][i]!=par[v][i]) { u=par[u][i]; v=par[v][i]; } return (par[u][0]); } void process(void) { REP(zz,q) { int u,v; scanf("%d%d",&u,&v); printf("%d\n",LCA(getMinLabel(u,v),getMaxLabel(u,v))); } } int main(void) { loadtree(); prepare(); process(); return 0; }
Comments