Untitled

mail@pastecode.io avatar
unknown
c_cpp
18 days ago
2.4 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

#define Task "DATA"
#define ll long long
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)

const int N = 5e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

template<class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }

int m = 0;
vector<int> adj[N];
ll dp[N];
bool isBlocked[N];
int st[N], en[N];

struct Fenwick {
    int bit[N + 1];

    void update(int idx, int val) {
        while (idx <= N) {
            bit[idx] += val;
            idx += (idx & (-idx));
        }
    }

    int get(int idx) {
        int res = 0;
        while (idx > 0) {
            res += bit[idx];
            idx -= (idx & (-idx));
        }
        return res;
    }
};

Fenwick fen;

void dfs(int u, int p) {
    st[u] = ++m;
    for (int v : adj[u]) {
        if (v == p) continue;
        dp[v] = dp[u] * (adj[u].size() - (p != -1 ? 1 : 0)) % MOD;
        dfs(v, u);
    }
    en[u] = m;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(Task".INP", "r")) {
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }

    int numNode, numQuery;
    cin >> numNode >> numQuery;
    FOR(i, 1, numNode - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dp[1] = 1;
    dfs(1, -1);
    while (numQuery--) {
        int t, u;
        cin >> t >> u;
        if (t == 1) {
            int numBlocked = fen.get(st[u]);
            if (numBlocked > 0) {
                if (numBlocked == 1 && isBlocked[u]) cout << 1 << " " << dp[u] << "\n";
                else cout << 0 << "\n";
            }
            else if (adj[u].size() > 1 && !isBlocked[u]) cout << 0 << "\n";
            else cout << 1 << " " << dp[u] << "\n";
        } else {
            isBlocked[u] ^= 1;
            int x = (isBlocked[u] ? 1 : -1);
            fen.update(st[u], x);
            fen.update(en[u] + 1, -x);
        }
    }

    return 0;
}


Leave a Comment