DP trên cây: chọn đỉnh không kề và gộp nhánh tìm đường kính

Từ dãy một chiều tới cấu trúc phân nhánh

Bài chọn các phần tử không kề nhau trên dãy chỉ cần nhớ hai tiền tố gần nhất. Trên cây, mỗi đỉnh có thể nối với nhiều con. Nếu chọn một đỉnh, ta phải kiểm điều kiện với tất cả các con, còn mỗi con lại quản lý cả một nhánh lớn phía dưới.

Cây không có chu trình nên sau khi chọn gốc, bỏ cạnh nối u với cha làm nhánh của u tách biệt khỏi phần còn lại. Thông tin giao tiếp nằm ở ranh giới này. DP trên cây thiết kế trạng thái mô tả đủ điều kiện ở u, rồi gộp kết quả các con khi các nhánh không còn tương tác trực tiếp với nhau.

Dữ liệu ví dụ có cạnh 0–1, 0–2, 1–3, 1–4 và trọng số [5,1,4,3,2]. Gốc 0 chỉ phục vụ tổ chức tính; với bài tối đa trên toàn cây, đáp án cuối không phụ thuộc việc chọn gốc nào nếu trạng thái và cách gộp đúng.

Tập độc lập có trọng số: phải nhớ lấy hay bỏ u

Tập độc lập là tập đỉnh không có hai đỉnh nào được nối trực tiếp bằng cạnh. Muốn tổng trọng số lớn nhất và được phép không chọn gì. Đặt take[u] là tổng tốt nhất trong cây con u khi bắt buộc chọn u; skip[u] là tổng tốt nhất khi không chọn u.

Nếu chọn u, mọi con v đều phải bị bỏ để không vi phạm cạnh u–v. Vì vậy take[u]=weight[u]+tổng skip[v]. Nếu bỏ u, mỗi nhánh con được tự chọn trạng thái tốt hơn, nên skip[u]=tổng max(take[v],skip[v]). Đáp án toàn cây là max hai trạng thái của gốc.

Chỉ lưu best[u]=max(take,skip) là chưa đủ cho cha. Khi cha được chọn, nó cần đúng trường hợp con bị bỏ, không được dùng tùy ý best của con. Đây là ví dụ điển hình cho việc trạng thái phải giữ điều kiện ở ranh giới, thay vì chỉ giữ đáp án tốt nhất tự do.

Chạy tay từ lá lên gốc

Lá không có con nên take bằng trọng số, skip bằng 0. Sau đó xử lý đỉnh 1 có hai con 3,4, rồi gốc 0 có hai con 1,2.

Kết quả 10 không phải chọn các trọng số lớn nhất mà bỏ qua vị trí. Đỉnh 2 có trọng số 4 nhưng kề gốc 0 đang chọn, nên không được ghép vào phương án 10. Nếu bỏ 0 thì có thể lấy 2 cùng phương án tốt của nhánh 1, được 9.

Nếu mọi trọng số bằng 1, bài trở thành tìm số đỉnh lớn nhất trong một tập độc lập. Nếu trọng số có thể âm và cho phép chọn rỗng, skip ở lá bằng 0 giúp bỏ đỉnh âm. Đề bắt buộc chọn ít nhất một đỉnh cần cơ sở hoặc trạng thái phù hợp riêng; code dùng quy ước được chọn rỗng.

Đường kính: hai nhánh tốt nhất gặp nhau tại u

Đường kính cây không trọng số là số cạnh lớn nhất trên một đường đơn. Đặt down[u] là số cạnh của nhánh dài nhất bắt đầu ở u và đi xuống cây con. Với lá, down=0. Mỗi con v tạo nhánh dài down[v]+1.

Giữ hai độ dài lớn nhất từ hai con khác nhau. Đường dài nhất có điểm cao nhất là u sẽ ghép hai nhánh đó, độ dài first+second. Nếu chỉ có một con, nhánh còn lại dài 0; nếu là lá, cả hai bằng 0. Lấy max trên mọi u cho đường kính toàn cây, không chỉ đọc down của gốc.

Trong hình, down[3],down[4],down[2] đều 0. Đỉnh 1 có hai nhánh dài 1 nên có đường 3–1–4 dài 2 và down[1]=1. Ở gốc 0, nhánh qua 1 dài 2, qua 2 dài 1; ghép được đường kính 3, chẳng hạn 3–1–0–2.

Không lấy hai nhánh tốt nhất từ cùng một con, vì như vậy đường sẽ quay qua cùng cạnh và không còn là đường đơn đi qua u theo cấu trúc đang xét. Thông tin down của con chỉ đại diện một nhánh đi xuống; nếu cần đường tốt nhất hoàn toàn bên trong con, kết quả toàn cục đã được cập nhật khi xử lý con đó.

Code C++ và Python không dùng đệ quy sâu

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
long long independent_set(const vector<long long>& weight,const vector<pair<int,int>>& edges){
    int n=weight.size();if(n==0)return 0;
    vector<vector<int>> g(n);
    for(auto [u,v]:edges){g[u].push_back(v);g[v].push_back(u);}
    vector<int> parent(n,-1),order={0};parent[0]=0;
    for(int i=0;i<(int)order.size();++i){
        int u=order[i];for(int v:g[u])if(parent[v]==-1){parent[v]=u;order.push_back(v);}
    }
    vector<long long> take=weight,skip(n,0);
    for(int i=n-1;i>=0;--i){
        int u=order[i];
        for(int v:g[u])if(parent[v]==u){
            take[u]+=skip[v];skip[u]+=max(take[v],skip[v]);
        }
    }
    return max(take[0],skip[0]);
}
int diameter(int n,const vector<pair<int,int>>& edges){
    if(n==0)return 0;
    vector<vector<int>> g(n);
    for(auto [u,v]:edges){g[u].push_back(v);g[v].push_back(u);}
    vector<int> parent(n,-1),order={0};parent[0]=0;
    for(int i=0;i<(int)order.size();++i){
        int u=order[i];for(int v:g[u])if(parent[v]==-1){parent[v]=u;order.push_back(v);}
    }
    vector<int> down(n,0);int answer=0;
    for(int i=n-1;i>=0;--i){
        int u=order[i],first=0,second=0;
        for(int v:g[u])if(parent[v]==u){
            int value=down[v]+1;
            if(value>first){second=first;first=value;}
            else if(value>second)second=value;
        }
        down[u]=first;answer=max(answer,first+second);
    }
    return answer;
}
int main(){
    int n=5;vector<long long> w={5,1,4,3,2};vector<pair<int,int>> e={{0,1},{0,2},{1,3},{1,4}};
    if(cin>>n){w.resize(n);for(auto& x:w)cin>>x;e.resize(max(0,n-1));for(auto& [u,v]:e)cin>>u>>v;}
    cout<<independent_set(w,e)<<' '<<diameter(n,e)<<'\n';
}

import sys

def independent_set(weight,edges):
    n=len(weight)
    if not n:
        return 0
    g=[[] for _ in range(n)]
    for u,v in edges:
        g[u].append(v);g[v].append(u)
    parent=[-1]*n;parent[0]=0;order=[0]
    for u in order:
        for v in g[u]:
            if parent[v]==-1:
                parent[v]=u;order.append(v)
    take=weight[:];skip=[0]*n
    for u in reversed(order):
        for v in g[u]:
            if parent[v]==u:
                take[u]+=skip[v];skip[u]+=max(take[v],skip[v])
    return max(take[0],skip[0])

def diameter(n,edges):
    if not n:
        return 0
    g=[[] for _ in range(n)]
    for u,v in edges:
        g[u].append(v);g[v].append(u)
    parent=[-1]*n;parent[0]=0;order=[0]
    for u in order:
        for v in g[u]:
            if parent[v]==-1:
                parent[v]=u;order.append(v)
    down=[0]*n;answer=0
    for u in reversed(order):
        first=second=0
        for v in g[u]:
            if parent[v]==u:
                value=down[v]+1
                if value>first:
                    first,second=value,first
                elif value>second:
                    second=value
        down[u]=first;answer=max(answer,first+second)
    return answer

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    w=[5,1,4,3,2];edges=[(0,1),(0,2),(1,3),(1,4)]
    if a:
        n=a[0];w=a[1:1+n];i=1+n
        edges=[tuple(a[i+2*j:i+2*j+2]) for j in range(max(0,n-1))]
    print(independent_set(w,edges),diameter(len(w),edges))

Không nhập dữ liệu, chương trình in 10 3: tổng tập độc lập tối ưu và đường kính theo số cạnh. Input riêng có n, tiếp theo n trọng số, sau đó n−1 cạnh vô hướng khi n dương. Nhãn đỉnh từ 0 tới n−1. Dữ liệu phải thật sự là cây liên thông; không đưa đồ thị có chu trình hoặc rời rạc rồi coi bảng cha này là lời giải cho bài tổng quát.

Tệp quy ước n=0 cho hai kết quả 0. Với một đỉnh, đường kính 0, còn tập độc lập chọn max(0,weight). Trọng số và mọi tổng C++ cần vừa long long. Python có số nguyên lớn nhưng số đỉnh và bộ nhớ vẫn phải phù hợp giới hạn hệ thống.

Hai hàm dựng danh sách parent và order bằng một lượt đi từ gốc. Cha luôn vào order trước con; đảo order cho thứ tự con trước cha. Ta không cần thứ tự hậu duyệt giống hệt một DFS đệ quy cụ thể, chỉ cần mọi quan hệ phụ thuộc được tôn trọng trước khi gộp.

Vì sao các nhánh có thể tối ưu độc lập?

Trong cây, hai cây con khác nhau của u không có cạnh nối trực tiếp với nhau. Nếu có, cạnh đó cùng các đường qua u sẽ tạo chu trình. Khi trạng thái của u đã cố định, ràng buộc chọn đỉnh ở nhánh này không làm thay đổi trạng thái khả thi ở nhánh kia, nên có thể cộng các tối ưu con phù hợp.

Trên đồ thị có thêm cạnh giữa hai nhánh, cách cộng này có thể chọn hai đỉnh đang kề nhau mà không biết. Vì vậy cây không chỉ là một input dễ vẽ; tính không chu trình là phần của chứng minh. Không dùng cùng công thức cho đồ thị bất kỳ chỉ sau khi chọn một cây DFS và bỏ qua các cạnh còn lại.

Với bài có tài nguyên chung, chẳng hạn tổng số công việc chọn không vượt K, các nhánh không thể tối ưu riêng một con số rồi cộng. Cần trạng thái theo lượng tài nguyên và gộp như cái túi giữa các cây con. Chính yêu cầu kết hợp qua ranh giới quyết định số chiều DP.

Đường kính, reroot và các biến thể

Tìm một đường kính có thể làm bằng hai lượt BFS trên cây không trọng số; DP hai nhánh là một cách khác giúp học cách gộp con. Nếu đề hỏi khoảng cách xa nhất từ từng đỉnh, chỉ down[u] tính theo một gốc chưa đủ vì đường tốt nhất có thể đi lên phía cha. Cần thêm thông tin từ ngoài cây con, thường gặp trong kỹ thuật reroot.

Đề cây có trọng số còn cần chốt trọng số có âm không và có cho đường rỗng không. Đường kính đếm cạnh của code hiện tại không cộng trọng số cạnh; trọng số nhập trong ví dụ là giá trị để chọn đỉnh, không phải chiều dài các cạnh. Hai loại dữ liệu được dùng cho hai mục tiêu khác nhau, không được tráo vai trò.

Bài đếm số cách chọn tập độc lập cũng giữ trạng thái chọn/bỏ, nhưng phép gộp số cách thường là nhân giữa các nhánh rồi cộng các lựa chọn thay thế. Không dùng tổng trọng số tối đa của code này để trả lời số cách; đó là một hệ phép toán và cơ sở khác.

Độ phức tạp và cách tự kiểm tra

Mỗi hàm duyệt các đỉnh và các mục danh sách kề một số lần hằng số, nên O(n) thời gian, O(n) bộ nhớ trên cây. Gọi cả hai hàm vẫn O(n), dù có phần dựng cha lặp lại. Nếu muốn giảm hằng số, có thể dùng chung parent, order nhưng không cần để hiểu công thức.

Để tự kiểm tra trên cây nhỏ (n ≤ 12), với bài tập độc lập trọng số lớn nhất bạn có thể duyệt mọi tập con đỉnh bằng bitmask và loại các tập chứa hai đầu mút của cùng một cạnh; với bài đường kính cây bạn có thể chạy BFS từ từng đỉnh rồi lấy khoảng cách lớn nhất. Đừng quên thử cây một đỉnh (trọng số âm và dương), cây đường thẳng và cây hình sao.

Tự thử thêm cây dây, cây sao, toàn trọng số âm và toàn trọng số 1. Trên cây dây, kết quả chọn không kề phải khớp bài DP một chiều; trên cây sao, có thể so việc chọn tâm với tổng các lá. Hai hình dạng này giúp quan sát trạng thái rất rõ.

Luyện ngay trên Big-O Coding

Bài đường kính luyện cách ghép nhánh. Bài khoảng cách xa nhất từ mỗi đỉnh mở rộng sang thông tin phía cha và reroot. Bài công việc phụ thuộc trên cây thêm chiều tài nguyên, cần kết hợp kết quả các con như cái túi; nên làm sau khi đã vững hai trạng thái chọn/bỏ và thứ tự con trước cha.

Câu hỏi thường gặp

Nguồn tham khảo

• USACO Guide: DP on Trees
• CP-Algorithms: Depth First Search
• AtCoder DP: Independent Set