Tương tự như kỹ thuật Phân Chia Và Chinh Phục Theo Điểm, Phân Chia Và Chinh Phục Theo Cạnh cũng là một phương pháp giải quyết các bài toán liên quan đến đường đi trên cây. Tuy nhiên, trong khi Phân Chia Và Chinh Phục Theo Điểm tìm trọng tâm và xem xét các đường đi đi qua trọng tâm, thì Phân Chia Và Chinh Phục Theo Cạnh lại tìm "cạnh trọng tâm" (cạnh mà giá trị lớn nhất giữa hai cây con của nó là nhỏ nhất) và xem xét các đường đi đi qua cạnh này. Thông thường, việc giải bài toán bằng Phân Chia Và Chinh Phục Theo Cạnh sẽ dễ hình dung hơn, độ phức tạp cũng không phụ thuộc vào bậc của các đỉnh; trong khi cây Phân Chia Theo Điểm thường cần phải lo lắng về vấn đề bậc của các đỉnh.
Xử Lý Ba Độ
Tìm trực tiếp "cạnh trọng tâm" với độ phức tạp O(n²) là không đúng, vì nó có thể bị đồ thị hình hoa cúc làm chậm lại. Do đó, cần thực hiện xử lý ba độ. Đây cũng thường là một trong những phần khó nhất.
Có hai phương pháp phổ biến. Một là tạo một chuỗi các điểm ảo, mỗi điểm trên chuỗi có thể có một con (cạnh là cạnh ảo); phương pháp thứ hai là cách viết kiểu cây đoạn. Hiện tại tôi đã sử dụng phương pháp đầu tiên.
Điểm khó trong xử lý ba độ là cách xử lý trọng số của các điểm và cạnh ảo. Ta thường có thể coi chuỗi các điểm ảo và đỉnh hiện tại như một điểm, các cạnh giữa chúng như các cạnh bên trong điểm, và đặt trọng số theo yêu cầu của bài toán.
Mẫu Mã
void dfs_xay_dung(int cur, int cha) {
int last = 0;
for (unsigned int i = 0; i < vec[cur].size(); ++i) {
int den = vec[cur][i]; if (den == cha) continue;
if (!last) {
ThemCanh(cur, den, 1);
last = cur;
} else {
int moi = ++tong; val[moi] = val[cur];
ThemCanh(last, moi, 0); ThemCanh(moi, den, 1);
last = moi;
}
dfs_xay_dung(den, cur);
}
}
bool visited[N << 1];
int KichThuoc, maxKichThuoc, canh_goc, kichThuoc[N];
void tim_canh_goc(int cur, int cha) {
kichThuoc[cur] = 1;
for (int i = head[cur]; i; i = e[i].next) {
int den = e[i].den; if (den == cha || visited[i]) continue;
tim_canh_goc(den, cur); kichThuoc[cur] += kichThuoc[den];
int v = max(kichThuoc[den], KichThuoc - kichThuoc[den]);
if (v < maxKichThuoc) maxKichThuoc = v, canh_goc = i;
}
}
long long ketQua;
void lam_viec(int moi) {
visited[moi] = visited[moi ^ 1] = true;
int u = e[moi].den, v = e[moi ^ 1].den;
//lam gi do
if (kichThuoc[u] > 1) {
KichThuoc = kichThuoc[u], maxKichThuoc = tong;
tim_canh_goc(u, v);
lam_viec(canh_goc);
}
if (kichThuoc[v] > 1) {
KichThuoc = kichThuoc[v], maxKichThuoc = tong;
tim_canh_goc(v, u);
lam_viec(canh_goc);
}
}
int main() {
//nhập dữ liệu
tong = n;
dfs_xay_dung(1, 0);
KichThuoc = tong, maxKichThuoc = tong;//lỗi
tim_canh_goc(1, 0);
lam_viec(canh_goc);
//xuất kết quả
return 0;
}
Bài Tập Ví Dụ
Thực tế, hầu như bất kỳ bài toán nào về Phân Chia Theo Điểm cũng có thể làm ví dụ cho Phân Chia Theo Cạnh.
Đường Dài Nhất Trên Cây
Cho một cây có \(n\) đỉnh, tìm một đường đi trên cây sao cho tích giữa độ dài đường đi và giá trị nhỏ nhất trên các đỉnh của đường đi là lớn nhất.
Trong đó độ dài đường đi được định nghĩa là số đỉnh trên đường đi.
\(n \le 50000\)
(Rõ ràng có thể dùng DSU + đường kính cây, hoặc Phân Chia Theo Điểm + mảng cây)
Phân Chia Theo Cạnh + con trùng.
Đặt trọng số điểm ảo bằng trọng số điểm hiện tại, trọng số cạnh ảo bằng 0, trọng số cạnh thật bằng 1.
Kênh Thông
Cho ba cây mỗi cây có \(n\) đỉnh, trọng số cạnh không âm, tìm:
[\max_{u,v} { dis_1(u,v) + dis_2(u,v) + dis_3(u,v)} ]\(1 \le n \le 10^5,0 \le w \le 10^{12}\)
Xem xét làm với hai cây đầu tiên. Có thể thực hiện Phân Chia Theo Cạnh trên cây đầu tiên, sau đó xây cây ảo trên cây thứ hai và tìm đường kính có trọng số điểm. Độ phức tạp: \(O(n \log n)\).
Vậy với ba cây thì sẽ là Phân Chia Theo Cạnh xây cây ảo rồi trên cây ảo lại Phân Chia Theo Cạnh lại tiếp tục xây cây ảo
Lưu ý trọng số cạnh không âm, do đó đường kính có thể hợp nhất nhanh, do đó với hai cây có thể trực tiếp duyệt trên cây đầu tiên để liệt kê LCA, sau đó chuyển đổi \(dis\) thành trọng số điểm và ném vào cây thứ hai, hợp nhất đường kính trên cây thứ hai. Coi "đường kính của tập hợp điểm trên cây thứ hai" như một cấu trúc dữ liệu để duy trì.
Với ba cây có thể thực hiện Phân Chia Theo Cạnh trên cây đầu tiên, duyệt cây ảo DFS trên cây thứ hai, và duy trì đường kính trên cây thứ ba. Lưu ý do yêu cầu của Phân Chia Theo Cạnh phải là đường đi giữa điểm đen và điểm trắng, khi duy trì đường kính cây thứ ba cần phải duy trì riêng đường kính đen và đường kính trắng. Có thể chứng minh đường kính đen-trắng dài nhất nhất định được tạo bởi các điểm cuối của đường kính đen và đường kính trắng.
Độ phức tạp: \(O(n \log^2 n)\) (LCA trên trình tự Euler trên cây thứ ba, và điểm nghẽn nằm ở thao tác sort khi xây cây ảo)
Công Nghệ: Hợp Nhất Cây Phân Chia Theo Cạnh
Ghi lại các cạnh trọng tâm mỗi lần để tạo thành quan hệ cây sẽ tạo thành cây Phân Chia Theo Cạnh. Cây Phân Chia Theo Cạnh tương tự như cây Phân Chia Theo Điểm, nhưng còn chứa một số cạnh, tương tự như cây重构 của Kruskal. Các nút lá đều là điểm, các nút còn lại đều là cạnh. Ngoài ra, còn có một số tính chất hữu ích:
- Cây nhị phân
- Chiều cao cây là \(O(\log)\)
Hai tính chất này cho phép cây Phân Chia Theo Cạnh có thể hợp nhất như cây đoạn động. Nếu đảm bảo tổng kích thước các cây Phân Chia trước khi hợp nhất là \(O(n \log n)\), và sau khi hợp nhất hai cây thì loại bỏ chúng, không tham gia vào các lần hợp nhất khác thì độ phức tạp có thể đảm bảo là \(O(n \log n)\).
Ví dụ: Viết Bằng Phương Pháp Bực Bội
Cho hai cây \(T,T'\), tìm
[depth(x) + depth(y) - (depth(LCA(x , y)) + depth′ (LCA′ (x, y))) ]\(n \le 366666\)
Liệt kê \(LCA'(x,y)\), phần còn lại có thể chuyển hóa thành \(\frac 1 {2}(d_x+d_y+dis(x,y))\), xây dựng cây Phân Chia Theo Cạnh, với mỗi điểm \(x\) duy trì khoảng cách đến tất cả các nút tổ tiên (thực chất là "cạnh tổ tiên") cộng với \(d_x\). Duy trì cây Phân Chia Theo Cạnh động, ban đầu là một chuỗi, sau đó trong quá trình duyệt \(T'\) đồng thời hợp nhất cây Phân Chia, khi hợp nhất đồng thời thống kê đáp án qua mỗi "cạnh" trên cây Phân Chia (\(L + R',L'+R\)).
Độ phức tạp: \(O(n \log n)\)
Mã Quan Trọng
inline void xay_dung_chuoi(int cur) {
int last_p = cur, last_t = ++tong_total;
for (unsigned int _ = vec[cur].size() - 1; ~_; --_) {
++tong_total;
son[tong_total][huong[last_p]] = last_t;
max_gia_tri[last_t] = vec[cur][_] + val[cur];//lỗi
last_p = canh_ancestor[last_p]; last_t = tong_total;
}
root[cur] = tong_total;
}
int hop_nhat(int x, int y) {
if (!x || !y) return x^ y;
if (son[x][0] && son[y][1]) MAX(ketQua, max_gia_tri[son[x][0]] + max_gia_tri[son[y][1]] - ketQua_bo_qua);
if (son[x][1] && son[y][0]) MAX(ketQua, max_gia_tri[son[x][1]] + max_gia_tri[son[y][0]] - ketQua_bo_qua);
son[x][0] = hop_nhat(son[x][0], son[y][0]);
son[x][1] = hop_nhat(son[x][1], son[y][1]);
MAX(max_gia_tri[x], max_gia_tri[y]);
return x;
}
void dfs_tren_cay2(int cur, int cha, long long nwd) {
MAX(ketQua,(val[cur] - nwd) * 2);
xay_dung_chuoi(cur);
for (unsigned int _ = 0; _ < ve[cur].size(); ++_) {
int den = ve[cur][_], w = v[cur][_];
if (den == cha) continue;
dfs_tren_cay2(den, cur, nwd + w);
ketQua_bo_qua = nwd << 1;
root[cur] = hop_nhat(root[cur], root[den]);//lỗi
}
}
Công Nghệ: Cây Phân Chia Theo Cạnh Bền Vững
Vì cây Phân Chia Theo Cạnh có nhiều điểm tương đồng với cây đoạn, và cây đoạn có thể bền vững, cây Phân Chia Theo Cạnh cũng nên có thể bền vững.
Cây Phân Chia Theo Cạnh bền vững có thể được dùng như "cây chủ tịch" trên cây.
Ví dụ: Bash Có Cứu Ngày Không?
Một cây có \(n\) đỉnh, cạnh có trọng số. Còn một hoán vị \(p_i\) độ dài \(n\). Hai loại thao tác:
1 l r x: tính \(\sum_{i=l}^r dis(p_i,x)\)2 x: hoán vị \(p_x,p_{x+1}\)\(1 \le n,q \le 2 \cdot 10^5\)
Rõ ràng cây Phân Chia Theo Điểm có thể dễ dàng giải quyết loại bài toán này, dùng hai loại cây đoạn bất kỳ để duy trì là được. Tuy nhiên không gian là \(O(n \log^2 n)\.
Còn có một phương pháp dùng cây đoạn phân chia cây, nguyên lý là: \(ans = \sum_{i=l}^r dep_{p_i}+dep_{x}-2dep_{lca}\). Đánh dấu các cạnh từ \(p_i\) đến gốc và cạnh từ \(x\) đến gốc, tổng trọng số của các cạnh được đánh dấu hai lần chính là \(dep_{lca}\). Xây dựng cây chủ tịch theo \(p_i\) để duy trì số lần mỗi cạnh bị bao phủ, có thể đạt \(O(n \log^2 n)\) cho dữ liệu tĩnh. Phát hiện việc hoán vị \(p_x,p_{x+1}\) chỉ ảnh hưởng đến cây thứ \(x\), do đó chỉ cần sửa lại cây đó là được. Thời gian và không gian đều là \(O(n \log^2 n)\)
Tuy nhiên không gian đều quá lớn, không thể qua bài này. Nhưng phương pháp cây chủ tịch kia có một \(\log\) đến từ phân chia chuỗi, nếu chúng ta có thể cắt bỏ cái \(\log\) đó thì tốt rồi.
Xem xét dùng cây Phân Chia Theo Cạnh để làm bài toán này. Duy trì khoảng cách từ mỗi điểm đến các tổ tiên trong cây Phân Chia, cây chủ tịch (cây Phân Chia) duy trì tổng khoảng cách từ các nút con trái và phải trong cây Phân Chía đến nút này đến cây chủ tịch. Thao tác hoán vị giống phương pháp phân chia chuỗi, thao tác truy vấn thì trên cây chủ tịch từ gốc đến \(x\) để truy vấn, nguyên lý giống cây Phân Chia bình thường, cách viết giống cây chủ tịch.
Độ phức tạp thời gian và không gian: \(O(n \log n)\)
Mã Quan Trọng
void xay_lai(int cur, int cha)
void tim_goc(int cur, int cha)
int chieuSau[N];
long long trangThai[N];
vector<long long> vec[N];
void dfs_khoangCach(int cur, int cha, long long nwd, int t) {
trangThai[cur] |= (t << chieuSau[cur]); ++chieuSau[cur]; vec[cur].push_back(nwd);//lỗi
//DFS
}
void dfs_cay(int moi) {
visited[moi] = visited[moi ^ 1] = true;
int u = e[moi].den, v = e[moi ^ 1].den;
dfs_khoangCach(u, v, 0, 0), dfs_khoangCach(v, u, e[moi].val, 1);
//chia và trị
}
int con[NN][2], root_cay[N], tong_total, kichThuoc[NN];
long long tong[NN];
void them(int p, int nwd, int s, int last_cur, int &cur) {
cur = ++tong_total; con[cur][0] = con[last_cur][0], con[cur][1] = con[last_cur][1];//LỖI
if (nwd == chieuSau[p]) return ;
them(p, nwd + 1, s >> 1, con[last_cur][s & 1], con[cur][s & 1]);
int sn = con[cur][s & 1], lsn = con[last_cur][s & 1];
tong[sn] = tong[lsn] + vec[p][nwd];
kichThuoc[sn] = kichThuoc[lsn] + 1;
}
void sua(int p, int nwd, int s, int t, int last_cur, int &cur) {//LỖI
cur = ++tong_total; con[cur][0] = con[last_cur][0], con[cur][1] = con[last_cur][1];
if (nwd == chieuSau[p]) return ;
sua(p, nwd + 1, s >> 1, t, con[last_cur][s & 1], con[cur][s & 1]);
int sn = con[cur][s & 1], lsn = con[last_cur][s & 1];
tong[sn] = tong[lsn] + t * vec[p][nwd];
kichThuoc[sn] = kichThuoc[lsn] + t;
}
long long truyVan(int p, int nwd, int s, int add_cur, int del_cur) {
if (nwd == chieuSau[p]) return 0;
int asn = con[add_cur][s & 1], dsn = con[del_cur][s & 1];
long long res = truyVan(p, nwd + 1, s >> 1, asn, dsn);
int dir = (s & 1) ^ 1;
asn = con[add_cur][dir], dsn = con[del_cur][dir];
res += (tong[asn] - tong[dsn]) + vec[p][nwd] * (kichThuoc[asn] - kichThuoc[dsn]);
return res;
}
int p[N];
int main() {
//nhập dữ liệu
xay_lai(1, 0);
KichThuoc = tong, maxKichThuoc = tong;
tim_goc(1, 0);
dfs_cay(canh_goc);
for (int i = 1; i <= n; ++i)
them(p[i], 0, trangThai[p[i]], root_cay[i - 1], root_cay[i]);
long long ketQua = 0;
for (int i = 1; i <= q; ++i) {
//nhập dữ liệu
if (t == 1) {
//nhập dữ liệu
ketQua = truyVan(x, 0, trangThai[x], root_cay[r], root_cay[l - 1]);
//xuất kết quả
} else {
//nhập dữ liệu
sua(p[x], 0, trangThai[p[x]], -1, root_cay[x], root_cay[x]);
swap(p[x], p[x + 1]);
sua(p[x], 0, trangThai[p[x]], 1, root_cay[x], root_cay[x]);
}
}
return 0;
}