大佬们救救孩子吧
查看原帖
大佬们救救孩子吧
921777
Koran楼主2023/1/5 22:42

我样例都过不了,自己查错,发现两次new出来的地址相同。

我该怎么办啊?!?!(有可能是因为其他原因引起的)

大佬们救救孩子吧,球球了(悲

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int maxN = 1e5 + 5;

int n, m;
vector<int> E[maxN];

struct Segment_tree {
    struct Node {
        Node *ch[2] = {nullptr};
        int sum = 0;

        void upd() {
            sum = 0;
            if (ch[0] != nullptr) sum += ch[0]->sum;
            if (ch[1] != nullptr) sum += ch[1]->sum;
        }
    } *root = nullptr;

    void modify(Node *&cur, int pos, int x, int L, int R) {
        if (cur == nullptr) cur = new Node;
        if (L == R) {
            cur->sum += x;
            return;
        }
        int mid = (L + R) >> 1;
        if (pos <= mid) modify(cur->ch[0], pos, x, L, mid);
        else modify(cur->ch[1], pos, x, mid + 1, R);
        cur->upd();
    }

    int query(Node *&cur, int l, int r, int L, int R) {
        if (l > r || cur == nullptr) return 0;
        if (l <= L && R <= r) return cur->sum;
        int mid = (L + R) >> 1, ans = 0;
        if (l <= mid) ans += query(cur->ch[0], l, r, L, mid);
        if (r > mid) ans += query(cur->ch[1], l, r, mid + 1, R);
        return ans;
    }

    Node *merge(Node *&p, Node *&q, int L, int R) {
        if (p == nullptr) return q;
        else if (q == nullptr) return p;
        Node *cur = new Node;
        cur->sum = p->sum + q->sum;
        if (L == R) return cur;
        int mid = (L + R) >> 1;
        cur->ch[0] = merge(p->ch[0], q->ch[0], L, mid);
        cur->ch[1] = merge(p->ch[1], q->ch[1], mid + 1, R);
        return cur;
    }
} smt[maxN];

void Dfs(int u, int fa, int d) {
    for (auto v : E[u]) {
        if (v == fa) continue;
        Dfs(v, u, d + 1);
        smt[u].root = smt[u].merge(smt[u].root, smt[v].root, 1, n);
    }
    smt[u].modify(smt[u].root, d, 1, 1, n);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        E[u].emplace_back(v);
        E[v].emplace_back(u);
    }
    Dfs(1, 0, 1);
    int lzj = n + 1;
    while (m--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) lzj = x;
        else cout << smt[x].query(smt[x].root, lzj, n, 1, n) << '\n';
    }

    return 0;
}
2023/1/5 22:42
加载中...