JZOJ 3745. 【NOI2014模拟7.14】Problem A

\(\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);
		}
	}
}