哪位大佬帮帮忙,我调的快要吐了也找不到问题。
#include<iostream>
#include <vector>
#include <string.h>
const int MAXN = 100007;
using namespace std;
struct info {
int top = 0, bot = 0, amt = 0;
void set(int a, int b, int c) { top = a, bot = b, amt = c; }
};
info T[MAXN << 2]; int lazy[MAXN << 2], top[MAXN], deep[MAXN], N, parent[MAXN], p[MAXN], heavy[MAXN], cur_pos;
vector<int> connect[MAXN];
void unlazy(int pos, int l, int r) {
if (!lazy[pos]) return; int mid = (l + r) >> 1;
lazy[pos << 1] = lazy[(pos << 1) + 1] = lazy[pos]; lazy[pos] = 0;
T[(pos << 1) + 1] = T[pos << 1] = T[pos];
T[pos << 1].amt = mid - l; T[(pos << 1) + 1].amt = r - mid - 1;
}
info query(int tr, int tl, int l, int r, int pos) {
if (l >= tl && r <= tr) return T[pos];
unlazy(pos, l, r); int mid = (l + r) >> 1, c = 0; info left, right;
if (tl <= mid) {c++; left = query(tr, tl, l, mid, pos << 1);}
if (tr > mid) { c += 2; right = query(tr, tl, mid + 1, r, (pos << 1) + 1); }
if (c == 1) return left;
if (c == 2) return right;
left.set(left.top, right.bot, left.amt + right.amt + (left.bot == right.top)); return left;
}
void update(int tr, int tl, int l, int r, int pos, int val) {
if (l >= tl && r <= tr) { lazy[pos] = val, T[pos].set(val, val, r - l); return; }
unlazy(pos, l, r); int mid = (l + r) >> 1;
if (tl <= mid) update(tr, tl, l, mid, pos << 1, val);
if (tr > mid) update(tr, tl, mid + 1, r, (pos << 1) + 1, val);
info left = T[pos << 1], right = T[(pos << 1) + 1];
T[pos].set(left.top, right.bot, left.amt + right.amt + (left.bot == right.top));
}
void ctree(int a, int b, int c) {
while (top[a] != top[b]) {
int ta = top[a], tb = top[b];
if (deep[ta] < deep[tb]) swap(a, b), swap(ta, tb);
update(p[a], p[ta], 1, N, 1, c);
a = parent[ta];
}
if (deep[a] < deep[b]) swap(a, b);
update(p[a], p[b], 1, N, 1, c);
}
int qtree(int a, int b) {
info left, right; bool isleft = false;
while (top[a] != top[b]) {
int ta = top[a], tb = top[b];
if (deep[ta] < deep[tb]) isleft = !isleft, swap(a, b), swap(ta, tb);
info z = query(p[a], p[ta], 1, N, 1);
if (isleft) left.set(z.top, left.bot, z.amt + left.amt + (z.bot == left.top));
else right.set(z.top, right.bot, z.amt + right.amt + (z.bot == right.top));
a = parent[ta];
}
if (deep[a] < deep[b])isleft = !isleft, swap(a, b);
info z = query(p[a], p[b], 1, N, 1), y = query(p[b], p[b], 1, N, 1);
if (isleft) {
left.set(z.top, left.bot, z.amt + left.amt + (z.bot == left.top));
right.set(y.top, right.bot, y.amt + right.amt + (y.bot == right.top));
}
else {
right.set(z.top, right.bot, z.amt + right.amt + (z.bot == right.top));
left.set(y.top, left.bot, y.amt + left.amt + (y.bot == left.top));
}
return right.amt + left.amt;
}
int dfs(int here, int from, int depth) {
int big = 0, x, sum = 1; deep[here] = depth; parent[here] = from;
for (int a : connect[here]) {
if (a == from) continue;
x = dfs(a, here, depth + 1);
if (big < x) heavy[here] = a, big = x;
sum += big;
}
return sum;
}
void decompose(int here, int h) {
p[here] = ++cur_pos; top[here] = h;
if (heavy[here])
decompose(heavy[here], h);
for (int a : connect[here]) {
if (a != parent[here] && a != heavy[here])
decompose(a, a);
}
return;
}
void initialize() {
cur_pos = 0; memset(p, 0, MAXN); memset(heavy, 0, MAXN); memset(parent, 0, MAXN);
memset(deep, 0, MAXN); memset(top, 0, MAXN);
for (int i = 0; i < MAXN; i++) connect[i].clear();
for (int i = 0; i < MAXN << 2; i++) T[i].set(0, 0, 0), lazy[i] = 0;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t, M, x, y, z; cin >> t;
while (t--) {
initialize();
cin >> N >> M;
for (int i = 0; i < N - 1; i++) {
cin >> x >> y;
connect[x].push_back(y); connect[y].push_back(x);
}
dfs(1, 0, 1);
decompose(1, 1);
}
}