我样例都过不了,自己查错,发现两次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;
}