\(\text{Problem}\)

我们有一个树，大小为 \(n\)。

考虑树上的一条路径，如果一个边的两个点都在这路径上，我们称这个边属于这个路径，如果一个边有且只有一个点在这路径上，我们称这个边与这个路径相邻。

现在每个边要么是黑色的要么是白色的，一开始所有边都是白色的。

我们有 \(3\) 个操作，将某路径反色，将与某路径相邻的所有边反色，求一个路径上黑边的总数。

\(\text{Solution}\)

第二个操作有点难。。。

从查询上想办法，发现树链剖分查询时跳过 \(O(log)\) 条重链和 \(O(log)\) 条轻边

启示我们维护一个点向下的重边有没有被反色过，向下的所有轻边有没有被反色过

显然需要线段树的区间修改

然后试着看能不能把操作不重不漏的修改完

发现还需要一个标记数组维护一个点向上的轻边有没有被反色过

查询过轻边时要结合标记数组和线段树信息弄出它真实的颜色

细节比较多

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#define RE register

#define IN inline

#define ls (p << 1)

#define rs (ls | 1)

using namespace std;

const int N = 1e5 + 5;

int n, m, a[N], h[N], tot;

struct edge{int nxt, to;}e[N << 1];

IN void add(int x, int y){e[++tot] = edge{h[x], y}, h[x] = tot;}

int top[N], fa[N], dfn[N], siz[N], son[N], dep[N], dfc;

void dfs1(int x, int y)

{

	siz[x] = 1, fa[x] = y, dep[x] = dep[y] + 1;

	for(int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == y) continue;

		dfs1(v, x), siz[x] += siz[v];

		if (siz[son[x]] < siz[v]) son[x] = v;

	}

}

void dfs2(int x, int t)

{

	top[x] = t, dfn[x] = ++dfc;

	if (son[x]) dfs2(son[x], t);

	for(int i = h[x]; i; i = e[i].nxt)

	{

		int v = e[i].to;

		if (v == fa[x] || v == son[x]) continue;

		dfs2(v, v);

	}

}

int bz[N], sum[N * 4], tg1[N * 4], tg0[N * 4];

IN void push(int p, int l, int r){sum[p] = r - l + 1 - sum[p], tg1[p] ^= 1;}

IN void pushdown(int p, int l, int r)

{

	int mid = l + r >> 1;

	if (tg1[p]) push(ls, l, mid), push(rs, mid + 1, r), tg1[p] = 0;

	if (tg0[p]) tg0[ls] ^= tg0[p], tg0[rs] ^= tg0[p], tg0[p] = 0;

}

void Modify(int p, int l, int r, int tl, int tr, int v)

{

	if (tr < l || r < tl) return;

	if (tl <= l && r <= tr){if (v) push(p, l, r); else tg0[p] ^= 1; return;}

	pushdown(p, l, r);

	int mid = l + r >> 1;

	if (tl <= mid) Modify(ls, l, mid, tl, tr, v);

	if (tr > mid) Modify(rs, mid + 1, r, tl, tr, v);

	sum[p] = sum[ls] + sum[rs];

}

int Query(int p, int l, int r, int tl, int tr, int v)

{

	if (tr < l || r < tl) return 0;

	if (tl <= l && r <= tr) return (v ? sum[p] : tg0[p]);

	pushdown(p, l, r);

	int mid = l + r >> 1, res = 0;

	if (tl <= mid) res = Query(ls, l, mid, tl, tr, v);

	if (tr > mid) res += Query(rs, mid + 1, r, tl, tr, v);

	return res;

}

int main()

{

	scanf("%d", &n);

	for(RE int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);

	dfs1(1, 0), dfs2(1, 1), scanf("%d", &m);

	for(RE int x, y, t, fx, fy; m; --m)

	{

		scanf("%d%d%d", &t, &x, &y), fx = top[x], fy = top[y];

		if (t == 1)

		{

			while (fx ^ fy)

				if (dep[fx] > dep[fy]) Modify(1, 1, n, dfn[fx], dfn[x] - 1, 1), bz[fx] ^= 1, x = fa[fx], fx = top[x];

				else Modify(1, 1, n, dfn[fy], dfn[y] - 1, 1), bz[fy] ^= 1, y = fa[fy], fy = top[y];

			if (x == y) continue;

			if (dep[x] > dep[y]) swap(x, y); Modify(1, 1, n, dfn[x], dfn[y] - 1, 1);

		}

		else if (t == 2){

			while (fx ^ fy)

				if (dep[fx] > dep[fy])

					Modify(1, 1, n, dfn[fx], dfn[x], 0), Modify(1, 1, n, dfn[x], dfn[x], 1), bz[fx] ^= 1, x = fa[fx], fx = top[x];

				else Modify(1, 1, n, dfn[fy], dfn[y], 0), Modify(1, 1, n, dfn[y], dfn[y], 1), bz[fy] ^= 1, y = fa[fy], fy = top[y];

			if (dep[x] > dep[y]) swap(x, y); Modify(1, 1, n, dfn[x], dfn[y], 0), Modify(1, 1, n, dfn[y], dfn[y], 1);

			if (x == top[x]) bz[x] ^= 1; else Modify(1, 1, n, dfn[fa[x]], dfn[fa[x]], 1);

		}

		else{

			t = 0;

			while (fx ^ fy)

				if (dep[fx] > dep[fy])

					t += Query(1, 1, n, dfn[fx], dfn[x] - 1, 1) + (bz[fx] ^ Query(1, 1, n, dfn[fa[fx]], dfn[fa[fx]], 0)), x = fa[fx], fx = top[x];

				else t += Query(1, 1, n, dfn[fy], dfn[y] - 1, 1) + (bz[fy] ^ Query(1, 1, n, dfn[fa[fy]], dfn[fa[fy]], 0)), y = fa[fy], fy = top[y];

			if (x ^ y && dep[x] > dep[y]) swap(x, y); t += Query(1, 1, n, dfn[x], dfn[y] - 1, 1);

			printf("%d\n", t);

		}

	}

}

巴特西

JZOJ 3745. 【NOI2014模拟7.14】Problem A

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章