Ta coi mỗi học sinh là một nút trong đồ thị và các mối quan hệ bạn bè là cạnh của đồ thị

Subtask 1

Ta sẽ sinh nhị phân để chia các học sinh thành 2 bên và tính tổng sức mạnh.

Subtask 2

Nhận xét: Độ chênh lệch sức mạnh giữa 2 nhóm bằng độ chênh lệch tổng bậc ở các nút chia ~2~

Giải thích: nếu một cạnh có giá trị là ~v~ nằm ở một nhóm thì tổng bâc ở nhóm đó được cộng thêm ~2v~, ngược lại nếu cạnh đó nối với 2 đỉnh ở 2 nhóm khác nhau thì tổng bậc ở mỗi nhóm sẽ được tăng thêm ~v~ và chênh lệch không hề thay đổi.

Vậy ta có công thức quy hoạch động ~dp[i][cnt][sum] = true/false~ tức là xét đến học sinh thứ ~i~ và đã lựa chọn ~cnt~ học sinh vào nhóm 1 trong số các học sinh từ ~1 \rightarrow i - 1~ và tổng bậc của nhóm 1 là ~sum~.

Cách chuyển trạng thái giống như bài toán quy hoạch động cái túi cơ bản nên xin nhường lại cho bạn đọc.

Độ phức tap: ~\mathcal{O}(n^4)~

Subtask 3

Hàm quy hoạch động của ta có thể dùng bitset để chuyển trạng thái nhanh hơn. Cụ thể các bạn có thể đọc comment này trên codeforces.