let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

solution.md

Sau đây là cách giải tham lam của bài này, có thể xem cách sử dụng quy hoạch động ở trên.

Từ comment của tác giả:

If a node has no coin then there must be a coin in at least one of its children (from this follows that there must be a coin in every leaf).

Do DFS maintaining the following state for each node:

  • count - the number of coins in the subtree rooted at that node
  • s - whether there is a coin in the node (1, 0 otherwise)
  • d - whether it requires a coin from an ancestor (0 - no, 1 - parent or grandparent, 2 - parent)

Place a coin in the node if there are no children with a coin or if there is a child demanding a coin from its parent (that includes any demand passed from a grandchild).

Cụ thể, sau khi gọi đệ quy các con của u, ta tính s và d như sau:

  • Nếu không có con nào của u được đặt xu hoặc có ít nhất một con của u có d = 2 thì ta đặt xu ở u (s = 1), và tính d như sau:
    • Nếu u là lá thì d = 1, ngược lại d = 0
  • Trong trường hợp ngược lại, ta không đặt xu ở u (s = 0), và tính d như sau:
    • Nếu có ít nhất một con của u cần đồng xu ở nút tổ tiên (có d khác 0) hoặc số con được đặt xu của u bé hơn 2 thì ta gán d của u bằng 2, ngược lại ta gán 0.
main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;
 
typedef vector<vector<int>> dsk;
struct pack {int count, s, d; };
 
pack dfs(int u, int p, const dsk &ke) {
    int count = 0, ss = 0, ws = 0, d = 0;
    for (int v : ke[u]) if (v != p) {
        pack r = dfs(v, u, ke);
        count += r.count;
        d = max(d, r.d);
        if (r.s) ss++;
        else ws++;
    }
 
    int ns, nd;
    if (ss == 0 || d == 2) {
        count++;
        ns = 1;
        if (ss || ws) nd = 0;
        else nd = 1;
    } else {
        ns = 0;
        if (d || ss < 2) nd = 2;
        else nd = 0;
    }
    return {count, ns, nd};
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        if (n == 1) {
            cout << "-1\n";
            continue;
        }
        dsk ke(n);
        while (--n) {
            int u, v; cin >> u >> v;
            u--, v--;
            ke[u].push_back(v);
            ke[v].push_back(u);
        }
        pack r = dfs(0, -1, ke);
        if (r.d > 0) r.count++;
        cout << r.count << '\n';
    }
    return 0;
}
Comments