Hướng dẫn cho Số đỏ

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một cấu trúc cây gồm \(n\) nút với gốc là nút \(1\). Mỗi nút \(u\) có một vách ngăn có thể đóng hoặc mở (ban đầu tất cả đều mở). Một viên bi được thả từ gốc \(1\):

Nếu nút hiện tại có vách ngăn đóng, viên bi dừng lại tại đó.
Nếu vách ngăn mở, viên bi sẽ rơi xuống một trong các nút con của nó với xác suất bằng nhau.
Nếu nút hiện tại là lá và vách ngăn mở, viên bi dừng lại tại đó.

Có \(q\) truy vấn thuộc hai loại:

Tính xác suất viên bi dừng lại tại nút \(u\).
Đảo trạng thái vách ngăn của nút \(u\) (đóng thành mở và ngược lại).

Phân tích

Điều kiện: \(n, q \leq 5 \times 10^5\). Thời gian giới hạn yêu cầu thuật toán tối ưu hơn \(O(n^2)\).
Xác suất dừng lại: Viên bi dừng lại tại nút \(u\) khi và chỉ khi:
1. Tất cả các nút trên đường đi từ gốc \(1\) đến cha của \(u\) đều có vách ngăn mở.
2. Nút \(u\) có vách ngăn đóng HOẶC nút \(u\) là nút lá (không có con).
Tính toán xác suất: Gọi \(deg(v)\) là số lượng nút con của nút \(v\). Nếu viên bi đi qua nút \(v\) và vách ngăn của \(v\) mở, xác suất nó rơi xuống một nút con cụ thể là \(\frac{1}{deg(v)}\).
Vậy xác suất để viên bi đến được nút \(u\) là:

\[ P(u) = \prod_{v \in \text{path}(1, \text{parent}(u))} \frac{1}{deg(v)} \]

Nếu có bất kỳ nút nào trên đường đi từ \(1\) đến cha của \(u\) bị đóng, xác suất viên bi đến được \(u\) là \(0\).

Cách làm đơn giản (Brute Force)

Với mỗi truy vấn loại 1, ta duyệt ngược từ \(u\) lên gốc \(1\). Nếu gặp bất kỳ nút nào bị đóng trên đường đi (ngoại trừ chính nút \(u\)), xác suất bằng \(0\). Nếu không, ta tính tích các \(deg(v)\) và trả về kết quả.

Độ phức tạp

Thời gian: \(O(q \times n)\) trong trường hợp cây suy biến thành đường thẳng.
Đánh giá: Phù hợp cho Subtask 1 (\(n, q \leq 1000\)).

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

int n, q;
vector<int> adj[500005];
int parent[500005];
bool is_closed[500005];
long long mod = 1e9 + 7;

void dfs_init(int u, int p) {
    parent[u] = p;
    for (int v : adj[u]) {
        if (v != p) dfs_init(v, u);
    }
}

int main() {
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_init(1, 0);
    while (q--) {
        int type, u; cin >> type >> u;
        if (type == 2) is_closed[u] = !is_closed[u];
        else {
            bool blocked = false;
            int curr = parent[u];
            while (curr != 0) {
                if (is_closed[curr]) { blocked = true; break; }
                curr = parent[curr];
            }
            if (blocked || (!is_closed[u] && (int)adj[u].size() - (u != 1) > 0)) {
                cout << 0 << "\n";
            } else {
                long long mau = 1;
                curr = parent[u];
                int temp = u;
                while (curr != 0) {
                    long long children = (int)adj[curr].size() - (curr != 1);
                    mau = (mau * children) % mod;
                    temp = curr;
                    curr = parent[curr];
                }
                cout << 1 << " " << mau << "\n";
            }
        }
    }
}

Python

import sys
sys.setrecursionlimit(10**6)

def solve():
    n, q = map(int, sys.stdin.readline().split())
    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)

    parent = [0] * (n + 1)
    def dfs(u, p):
        parent[u] = p
        for v in adj[u]:
            if v != p: dfs(v, u)
    dfs(1, 0)

    is_closed = [False] * (n + 1)
    MOD = 10**9 + 7

    for _ in range(q):
        line = list(map(int, sys.stdin.readline().split()))
        t, u = line[0], line[1]
        if t == 2:
            is_closed[u] = not is_closed[u]
        else:
            blocked = False
            curr = parent[u]
            while curr != 0:
                if is_closed[curr]:
                    blocked = True
                    break
                curr = parent[curr]

            num_children = len(adj[u]) - (1 if u != 1 else 0)
            if blocked or (not is_closed[u] and num_children > 0):
                print(0)
            else:
                mau = 1
                curr = parent[u]
                while curr != 0:
                    child_count = len(adj[curr]) - (1 if curr != 1 else 0)
                    mau = (mau * child_count) % MOD
                    curr = parent[curr]
                print(f"1 {mau}")
solve()

Hướng giải quyết (Tối ưu)

1. Quản lý các nút bị đóng

Để kiểm tra nhanh xem trên đường đi từ gốc đến cha của \(u\) có nút nào bị đóng hay không, ta có thể sử dụng kỹ thuật trải phẳng cây (Euler Tour) kết hợp với Binary Indexed Tree (BIT) hoặc Segment Tree.

Khi đóng/mở vách ngăn tại nút \(u\), ta thực hiện cập nhật trên đoạn \([tin[u], tout[u]]\) trong mảng Euler Tour.
Truy vấn loại 1 tại nút \(u\) sẽ kiểm tra tổng các giá trị trên đường đi từ gốc đến \(u\). Nếu tổng này (số lượng nút đóng trên đường đi) thỏa mãn điều kiện, ta mới tính xác suất.

2. Tính toán xác suất cố định

Xác suất dừng lại tại \(u\) (nếu không bị chặn ở trên) chỉ phụ thuộc vào cấu trúc cây:

Gọi \(P(u)\) là mẫu số của xác suất để viên bi rơi đến \(u\).
\(P(1) = 1\).
\(P(v) = P(u) \times deg(u)\) với \(v\) là con của \(u\).
Ta có thể tính trước toàn bộ giá trị \(P(u)\) bằng một lần DFS.

3. Điều kiện dừng lại tại \(u\)

Viên bi dừng lại tại \(u\) khi:

Không có nút nào từ \(1\) đến \(parent(u)\) bị đóng.
Và: \(u\) bị đóng HOẶC \(u\) là lá.
Lưu ý trường hợp đặc biệt: Nếu \(u\) bị đóng, ta chỉ quan tâm các nút phía trên nó. Nếu \(u\) mở, nó phải là lá thì bi mới dừng lại.

Độ phức tạp

Thời gian: \(O((n + q) \log n)\) do sử dụng DFS và BIT.
Bộ nhớ: \(O(n)\) để lưu cây và các mảng phụ trợ.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

const int N = 500010;
const long long mod = 1e9 + 7;

int n, q, times = 0;
vector<int> g[N];
pair<int, int> range_idx[N];
long long dp[N];
int bit[N], f[N];

void updatebit(int u, int val) {
    for (; u <= n; u += u & (-u)) bit[u] += val;
}

int getbit(int u) {
    int ans = 0;
    for (; u > 0; u -= u & (-u)) ans += bit[u];
    return ans;
}

void DFS(int u, int p, long long val) {
    dp[u] = val;
    range_idx[u].first = ++times;
    int children = g[u].size() - (u != 1);
    long long next_val = (children == 0) ? val : (val * children) % mod;
    for (int v : g[u]) {
        if (v != p) DFS(v, u, next_val);
    }
    range_idx[u].second = times;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    DFS(1, 0, 1);

    while (q--) {
        int loai, u; cin >> loai >> u;
        if (loai == 1) {
            // Số lượng nút đóng trên đường đi từ gốc đến u
            int closed_on_path = getbit(range_idx[u].first);
            // Bi dừng tại u nếu không có nút nào phía trên u đóng 
            // và (u đóng HOẶC u là lá)
            int num_children = g[u].size() - (u != 1);
            bool can_stop = (closed_on_path == (f[u] == 1)) && (f[u] == 1 || num_children == 0);

            if (can_stop) cout << 1 << " " << dp[u] << "\n";
            else cout << "0\n";
        } else {
            if (f[u] == 1) { // Đang đóng -> Mở
                updatebit(range_idx[u].first, -1);
                updatebit(range_idx[u].second + 1, 1);
                f[u] = 0;
            } else { // Đang mở -> Đóng
                updatebit(range_idx[u].first, 1);
                updatebit(range_idx[u].second + 1, -1);
                f[u] = 1;
            }
        }
    }
    return 0;
}

Python

import sys

# Tăng giới hạn đệ quy cho DFS
sys.setrecursionlimit(1000000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data: return

    n = int(input_data[0])
    q = int(input_data[1])
    adj = [[] for _ in range(n + 1)]

    idx = 2
    for _ in range(n - 1):
        u = int(input_data[idx])
        v = int(input_data[idx+1])
        adj[u].append(v)
        adj[v].append(u)
        idx += 2

    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    dp = [0] * (n + 1)
    timer = 0
    MOD = 10**9 + 7

    def dfs(u, p, val):
        nonlocal timer
        timer += 1
        tin[u] = timer
        dp[u] = val
        children_count = len(adj[u]) - (1 if u != 1 else 0)
        next_val = val
        if children_count > 0:
            next_val = (val * children_count) % MOD

        for v in adj[u]:
            if v != p:
                dfs(v, u, next_val)
        tout[u] = timer

    dfs(1, 0, 1)

    bit = [0] * (n + 2)
    def update(i, delta):
        while i <= n:
            bit[i] += delta
            i += i & (-i)

    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s

    is_closed = [0] * (n + 1)
    results = []

    for _ in range(q):
        t = int(input_data[idx])
        u = int(input_data[idx+1])
        idx += 2

        if t == 1:
            closed_above = query(tin[u])
            num_children = len(adj[u]) - (1 if u != 1 else 0)
            # Điều kiện: không có nút nào phía trên bị đóng
            # và (u bị đóng hoặc u là lá)
            if closed_above == is_closed[u] and (is_closed[u] == 1 or num_children == 0):
                results.append(f"1 {dp[u]}")
            else:
                results.append("0")
        else:
            if is_closed[u] == 1:
                update(tin[u], -1)
                update(tout[u] + 1, 1)
                is_closed[u] = 0
            else:
                update(tin[u], 1)
                update(tout[u] + 1, -1)
                is_closed[u] = 1

    sys.stdout.write("\n".join(results) + "\n")

solve()

Bình luận

Tải bình luận...

Không có bình luận nào.