Bài toán có dạng đồ thị dưới dạng cây (\(N\) đỉnh, \(N-1\) cạnh) có gốc tại đỉnh \(1\).

Trường hợp \(1 \le N, K \le 5000\)

• Gọi \(parent[v]\) là đỉnh thăm liền kề trước \(v\). Thực hiện \(DFS(1)\) để xác định \(parent[v]\) của tất cả các đỉnh \(v\) trong cây.
• Với mỗi đỉnh \(x\) Tâm chạm tay, robot sẽ xuất phát từ \(x\) đi đến các đỉnh thăm trước \(x\) (\(parent[x]\)) đến khi gặp đỉnh \(1\). Với mỗi đỉnh robot đi qua (ngoại trừ đỉnh \(1\) và đỉnh xuất phát \(x\)), thực hiện thay đổi trạng thái đèn của đỉnh.
• Sau khi thực hiện \(K\) lần chạm tay, đếm số đèn sáng.

Để đạt để tối đa sử dụng quy hoạch động:

Gọi \(dp[u]\) là số lần thay đổi trạng thái của đèn tại đỉnh \(u\)

• \(dp[u] =\) tổng tất cả các \(dp[v]\), với \(v\) là các đỉnh kề với \(u\).
• Thực hiện duyệt \(DFS(1)\) để tính \(dp[u]\)

Trạng thái đèn tại một địa điểm \(u\) (với \(u\) khác \(1\)) sáng trong hai trường hợp sau:

• Trạng thái đèn tại \(u\) ban đầu là \(1\) và \(dp[u]\) là số chẵn.
• Trạng thái đèn tại \(u\) ban đầu là \(0\) và \(dp[u]\) là số lẻ.

🚀 Thuật toán: Tính số đèn sáng sau K lần thao tác trong cây

🌐 Bài toán:

Cho cây N địa điểm, ban đầu mỗi điểm có đèn (\(0\): tắt, \(1\): sáng). Có \(K\) thao tác chạm tay tại đỉnh X_i. Mỗi thao tác làm đồng loạt đảo trạng thái các đỉnh từ X_i đến gốc (\(1\)). Hãy tính số địa điểm đang sáng cuối cùng.

🔍 Ý tưởng chiến lược:

✅ 1. Mô hình cây:

• Mỗi đỉnh có duy nhất 1 cha (cây gốc \(1\))
• Gọi tree[v] là danh sách con của v

✅ 2. Ánh xạ subtree bằng Euler Tour:

• Duyệt DFS, gán cho mỗi đỉnh:
  • in[u]: thời điểm vào
  • out[u]: thời điểm ra
• Khoảng [in[u], out[u]] là tập con đỉnh trong subtree(u)

✅ 3. Mỗi lần chạm tay tại X_i:

• Tăng freq[in[X_i]]++

✅ 4. Cộng dồn freq để tính số lần chạm đến mỗi subtree:

sum_freq[i+1] = sum_freq[i] + freq[i];

• Số lần chạm trong subtree(u): sum_freq[out[u]+1] - sum_freq[in[u]]
• Số lần chạm vào chính u: freq[in[u]]
• Số lần bị ảnh hưởng: total - self

🔄 5. Tính trạng thái cuối:

• Nếu số lần bị ảnh hưởng lẻ, thì đèn bị đảo: light[u] ^= 1
• Ngược lại giữ nguyên

📊 Độ phức tạp:

• DFS Euler Tour: \(O(N)\)
• K thao tác chạm tay: \(O(K)\)
• Duyệt tính trạng thái cuối: \(O(N)\)
• ⇒ Tổng O(N + K)

Thuật toán tối ưu nhờ biến việc chạm tay thành "số lần bị ảnh hưởng subtree", giải quyết hiệu quả bài toán tác động theo chiều ngược trong cây.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    // Trạng thái ban đầu của các đèn
    vector<int> state(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> state[i];

    // Cây: lưu danh sách con của mỗi đỉnh
    vector<vector<int>> tree(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        tree[v].push_back(u);
    }

    // Euler tour để gán thời điểm vào/ra mỗi đỉnh
    vector<int> in(N + 1), out(N + 1);
    int timer = 0;
    stack<pair<int, bool>> stk;
    stk.push({1, false});

    while (!stk.empty()) {
        auto [u, backtrack] = stk.top(); stk.pop();

        if (backtrack) {
            out[u] = timer++;
        } else {
            in[u] = timer++;
            stk.push({u, true});
            for (auto it = tree[u].rbegin(); it != tree[u].rend(); ++it)
                stk.push({*it, false});
        }
    }

    // freq[t] = số lần chạm vào đỉnh có thời điểm vào là t
    vector<int> freq(timer, 0);
    for (int i = 0; i < K; ++i) {
        int x; cin >> x;
        freq[in[x]]++;
    }

    // Tính mảng cộng dồn để truy vấn nhanh số lần tác động đến subtree
    vector<int> prefix(timer + 1, 0);
    for (int i = 0; i < timer; ++i)
        prefix[i + 1] = prefix[i] + freq[i];

    int result = 0;
    for (int u = 1; u <= N; ++u) {
        int total = prefix[out[u] + 1] - prefix[in[u]];  // tổng số lần chạm trong subtree
        int self = freq[in[u]];                          // số lần chạm vào chính u
        int toggle = total - self;

        // Nếu số lần bị ảnh hưởng lẻ → đảo trạng thái
        int final_state = (toggle % 2 == 0) ? state[u] : 1 - state[u];
        result += final_state;
    }

    cout << result << '\n';
    return 0;
}