为啥DFS会TLE
查看原帖
为啥DFS会TLE
466158
D3story楼主2021/8/27 02:40

哪位大佬帮帮忙,我调的快要吐了也找不到问题。

#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);
	}
}
2021/8/27 02:40
加载中...