树上换根板子求调,样例过完了,4 关
查看原帖
树上换根板子求调,样例过完了,4 关
720235
sigma_zjx楼主2024/10/9 10:28
#include <bits/stdc++.h>
using namespace std;
#define int long long

namespace sgt {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
	int sum[200005*8], tag[200005*8];
	void push_up(int i) {
		sum[i] = sum[ls(i)] + sum[rs(i)];
	}
	void build(const int *a, int i, int l, int r) {
		if (l == r) {
			sum[i] = a[l];
			return;
		}
		int mid = (l + r) / 2;
		build(a, ls(i), l, mid);
		build(a, rs(i), mid + 1, r);
		push_up(i);
	}
	void settag(int i, int l, int r, int k) {
		sum[i] += (r - l + 1) * k;
		tag[i] += k;
	}
	void push_down(int i, int l, int r) {
		if (!tag[i]) return;
		int mid = (l + r) / 2;
		settag(ls(i), l, mid, tag[i]);
		settag(rs(i), mid + 1, r, tag[i]);
		tag[i] = 0;
	}
	void update(int i, int l, int r, int ql, int qr, int k) {
		if (l > qr || r < ql) return;
		if (l >= ql && r <= qr) return settag(i, l, r, k);
		int mid = (l + r) / 2; push_down(i, l, r);
		update(ls(i), l, mid, ql, qr, k);
		update(rs(i), mid + 1, r, ql, qr, k);
		push_up(i);
	}
	int query(int i, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return 0;
		if (l >= ql && r <= qr) return sum[i];
		int mid = (l + r) / 2; push_down(i, l, r);
		return query(ls(i), l, mid, ql, qr) + query(rs(i), mid + 1, r, ql, qr);
	}
}

int n, q, ans[200005];
vector<int> edges[200005];
vector<pair<int, int>> qrs[200005];

namespace tr {
	int fa[21][200005], dep[200005], sz[200005], dfn[200005], dft, b[200005];
	void init(int i) {
		sz[i] = 1; dfn[i] = ++dft;
		for (auto j : edges[i]) {
			if (j == fa[0][i]) continue;
			fa[0][j] = i;
			dep[j] = dep[i] + 1;
			init(j);
			sz[i] += sz[j];
		}
		for (int j = 1; j <= 20; ++j) {
			fa[j][i] = fa[j - 1][fa[j - 1][i]];
		}
	}
	int jump(int x, int k) {
		for (int l = 0; k; ++l, k >>= 1)
			if (k & 1) x = fa[l][x];
		return x;
	}
	int query_son(int i, int minus) {
		return sgt::query(1, 1, n, dfn[i], dfn[i] + sz[i] - 1);
	}
	void update_t(int i, int k) {
		sgt::update(1, 1, n, dfn[i], dfn[i] + sz[i] - 1, k);
	}
	int lca(int x, int y) {
		if (dep[x] < dep[y]) swap(x, y);
		x = jump(x, dep[x] - dep[y]);
		int l = 20;
		while (~l) {
			if (fa[l][x] != fa[l][y]) {
				x = fa[l][x];
				y = fa[l][y];
			}
			--l;
		}
		return fa[0][x];
	}
	void dfs(int i) {
		assert(sgt::query(1, 1, n, dfn[i], dfn[i]) == 0);
		for (auto _ : qrs[i]) {
			int id = _.first,p = _.second;
			if (p < 0) p = -p, ans[id]+=sgt::sum[1]-query_son(p, 0);
			else ans[id]+=query_son(p, 0);
		}
		for (auto j : edges[i]) {
			if (j == fa[0][i]) continue;
			// 子树 -1,其他 +1 = 子树 -2, 整体 +1
			update_t(j, -2);
			update_t(1, +1);
			dfs(j);
			update_t(j, +2);
			update_t(1, -1);
		}
	}
	void preinit() {
		init(1);
		for (int i = 1; i <= n; ++i) b[dfn[i]] = dep[i];
		sgt::build(b, 1, 1, n);
	}
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	cin >> q;
	tr::preinit();
	for (int i = 1; i <= q; ++i) {
		int x, y;
		cin >> x >> y;
		if (tr::dep[x] < tr::dep[y]) swap(x, y);
		int lca = tr::lca(x, y);
		int mid = tr::jump(x, (tr::dep[x] + tr::dep[y] - 2 * tr::dep[lca] - 1) / 2);
		qrs[x].push_back({i, mid});
		qrs[y].push_back({i, -mid});
	}
	tr::dfs(1);
	for (int i = 1; i <= q; ++i) cout << ans[i] << "\n";
	return 0;
}

https://atcoder.jp/contests/abc298/submissions/58578342

2024/10/9 10:28
加载中...