树上问题乱做

2023-10-11 19:10:28

DFS序

DFS 序就是DFS得到的序列（简洁明了）

DFS 序擅长处理子树的问题， 可以发现 子树是这个子树根节点入栈到出栈的整个序列

DFS 序把子树修改转化为了区间修改的问题。

「HAOI2015」树上操作

要对一个树进行操作， 支持点修改， 子树修改， 查询某个节点到跟节点的距离。

对于树剖就是版子题， 但是我太菜了， 所以只好用 DFS 序解决。

前两个操作， 用 DFS 序可以轻松结局。 但是对于第三个操作需要认真的思考。

如何求点到根的距离成为了本题的关键。

观察节点 x 到根的DFS序的关系， 可以发现凡是在 1 ~ x 之间的出栈了的节点都没有在这条路径上， 那就可以把已经出栈的节点的权值抵消掉再求前缀和。

所以把入栈标记为 1， 把出栈标记为 -1。

用线段树维护这个序列。

对于操作一， 入栈增加 a， 出栈增加 -a。

对于操作二，用线段树进行区间修改， 用懒惰标记优化。

对于操作三，直接求 1 - in[x] 的前缀和。

// the code is from zxy
const int N = 100010;
typedef long long ll;
struct node {ll v, f; } d[N << 1];
struct G {ll dis, next;} edge[N << 1];
ll head[N + 1], siz;
inline void add (ll from, ll dis) {
	edge[++siz].dis = dis;
	edge[siz].next = head[from];
	head[from] = siz;
}
ll n, m;
ll a[N + 1], in[N + 1], out[N + 1],  S, sum[N << 1];
struct TREE {
	#define lson l, m, rt << 1
	#define rson m + 1, r, rt << 1 | 1
	#define ls rt << 1
	#define rs rt << 1 | 1
	ll val[N << 3], tag[N << 3];
	#define val(rt) val[rt]
	#define tag(rt) tag[rt]
	
	inline void pushup(ll rt) {val(rt) = val(ls) + val(rs);}
	inline void pushdown(ll l, ll m, ll r, ll rt) {
		if (!tag(rt)) return;
		val(ls) += tag(rt) * (sum[m] - sum[l - 1]), val(rs) += tag(rt) * (sum[r] - sum[m]);
		tag(ls) += tag(rt), tag(rs) += tag(rt), tag(rt) = 0;
	}
	inline void build(ll l, ll r, ll rt) {
		if (l == r) {val(rt) = d[l].f * a[d[l].v]; return;}
		ll m = l + r >> 1;
		build(lson), build(rson);
		pushup(rt);
	}
	// 单点修改 
	inline void update(ll pos, ll V, ll l, ll r, ll rt) {
		val(rt) += V;
		if (l == r) return ;
		ll m = l + r >> 1;
		if (pos <= m) update(pos, V, lson);
		else update(pos, V, rson);
	}
	// 区间修改 
	inline void update2(ll L, ll R, ll V, ll l, ll r, ll rt) {
		if (L <= l && r <= R) {
			tag(rt) += V;
			val(rt) += (ll) (V * (sum[r] - sum[l - 1]));
			return ;
		}
		ll m = l + r >> 1;
		pushdown(l, m, r, rt);
		if (L <= m) update2(L, R, V, lson);
		if (R > m) update2(L, R, V, rson);
		pushup(rt); 
	}
	inline ll ask(ll L, ll R, ll l, ll r, ll rt) {
		if (L <= l && r <= R) return val(rt);
		ll m = l + r >> 1;
		ll ans = 0;
		pushdown(l, m, r, rt);
		if (L <= m) ans += ask(L, R, lson);
		if (R > m)  ans += ask(L, R, rson);
		return ans;
	}
} tree;
inline void dfs(ll fa, ll u) {
	S++, in[u] = S, d[S].f = 1, d[S].v = u;
	for (ll i = head[u]; i; i = edge[i].next) if (fa != edge[i].dis) dfs(u, edge[i].dis);
	S++, out[u] = S,  d[S].f = -1, d[S].v = u;
}
int main() {
	scanf("%lld%lld", &n, &m);
	for (ll i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for (ll i = 1, v, u; i < n; i++) scanf("%lld%lld", &u, &v), add(u, v), add(v, u);
	dfs(0, 1);
	for (ll i = 1; i <= S; i++) sum[i] = sum[i - 1] + d[i].f;
	n <<= 1;
	tree.build(1, n, 1);
	while (m--) {
		ll op, x, A; scanf("%lld %lld", &op, &x);
		if (op == 1) {
			scanf("%lld", &A);
			tree.update(in[x], A, 1, n, 1);
			tree.update(out[x], -A, 1, n, 1);
		} else if (op == 2) {
			scanf("%lld", &A);
			tree.update2(in[x], out[x], A, 1, n, 1);
		} else printf("%lld\n", tree.ask(1, in[x], 1, n, 1));
	}	
	return 0;
}

代码长度就不说了。

树上差分

树上差分， 顾名思义就是在树上的差分， 适合修改树上任意路径的值。

点差分

设 p[u] 表示经过 u 和 u 的祖先节点的次数。

设 f[u] 表示经过 u 的次数。
$$
如果用 siz_u 表示这个子树的大小，那么 f_u = p_u+ \sum_{v = 1}^{siz_u}f_v
$$
对于修改 x, y 这条路径，即让这个路径上的数全部加上 d，只需要修改四个值 ：

p[x] += d, p[y] += d;
p[lca(x, y)] -=d, p[fa[lca(x, y)]] -= d;

对于前两个操作就是让 1 - x， 1 - y 这两段加上 d， 显然我们只想让 lca(x, y) 到x， y的这一段修改，不希望lca(x,y)以上的段修改。

所以就有了后两个操作，先删除一次 lca(x,y) 到根节点这一段， 由于 x 到 y 的这一段包括了 lca(x, y) 所以我们只好再减去 fa[lca(x, y)] 到根节点的这一段， 保证路径都只有一段被修改。

这个差分的操作使路径修改成为了常数级别。

「JLOI2014」松鼠的新家

模板题。维尼到达一个点， 这个点就多需要一个糖果， 所以问题简化成维尼每到达一个点， 这个点的权值就需要增加 1。 还要在特判一下， 第一个点要减去 1， 因为维尼是从这里开始走的。

// the code is from zxy
const int N = 300000;
struct node {
	int dis, next;
} edge[N << 1];
int siz, head[N + 1];
inline void add(int from, int dis) {
	edge[++siz].dis = dis;
	edge[siz].next = head[from]; 
	head[from] = siz;
}
int d[N];
int f[N + 1][30];
inline int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = 23; i >= 0; i--) if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i = 23; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
inline void dfs(int u, int fa) {
	d[u] = d[fa] + 1;
	f[u][0] = fa;
	for (int i = 1; (1 << i) <= d[u]; i++) f[u][i] = f[f[u][i - 1]][i - 1];
	for (int i = head[u]; i; i = edge[i].next) if (edge[i].dis != fa) dfs(edge[i].dis, u);
}
int c[N + 1];
int n, ans[N + 1], a[N + 1];
inline int find(int u) {
	ans[u] = c[u];
	for (int i = head[u]; i; i = edge[i].next) 
		if (edge[i].dis != f[u][0]) ans[u] += find(edge[i].dis); 
	return ans[u];
}
int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v);
		add(u, v); add(v, u);
	}
	dfs(1, 0);
	for (int i = 1; i < n; i++) {
		int l = lca(a[i], a[i + 1]);
		c[l]--, c[f[l][0]]--;
		c[a[i]]++, c[a[i + 1]]++;
	}
	find(1);
	for (int i = 1; i <= n; i++) {
		if (i != a[1]) ans[i]--;
		printf("%d\n", ans[i]);
	}
	return 0;
}

边差分

类似的。

对于边差分。
$$
我们设 f_u 表示经过点u和u的祖先的边的次数。
$$
如果要让 x 到 y 的边权加 d

f[x]++, f[y]++;
f[lca(x, y)] -= 2;

不同于点差分，边差分不需要算重复的 lca(x, y)， 直接让那条边减去多统计的2次就好了。

「POJ3417」暗的连锁

一个无向图有两种边， 切断一条主要边 和一条附加边， 使这个图不连通， 求方案数量。

可以发现主要边是一个树。而附加边似乎是多余的。

如何判断联通是本题的关键， 观察下图：

树上问题乱做

蓝色的是主要边， 暗红色的是附加边， 下图中打勾的是可以删除的， 打叉的是不可以删除的。

树上问题乱做

可以发现主要边这个树因为有了附加边出现了环， 这里环代表多条主要边和一条附加边。如上图中环就有:
$$
1\ 2\ 5, 2\ 3\ 5, 1\ 2\ 4\ 6 \dots
$$
观察发现无法删除的只是存在于多个环中的边。

考虑一条边没有在环里，删除这条边后，任意删除一条附加边都可以使图不连通， 方案书就是 m

一条边出现在一个环里，删除这条边后，附加边的删除是唯一的，方案数就是 1

一条边出现在多个环里，删除这条边后，无论删除那条附加边都无法使图不连通，方案数为 0。

那如何维护环的加减呢？

可以借助边差分的力量。

既然环是只有一条附加边，那每出现一条附加边就可以先用差分维护出现次数。

// the code is from zxy
const int N = 500100;
struct node {int dis, next;} edge[N + 1];
int siz, head[N + 1];
int n, m, u, v, ans;
inline void add(int from, int dis) {
	edge[++siz].dis = dis;
	edge[siz].next = head[from]; 
	head[from] = siz;
}
int f[N + 1][30], d[N + 1], p[N + 1];
inline void bfs() {
	queue<int> q; q.push(1); d[1] = 1;
	while (!q.empty()){
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = edge[i].next) {
			int dis = edge[i].dis;
			if (d[dis]) continue;
			d[dis] = d[u] + 1;
			f[dis][0] = u;
			for (int j = 1; j <= 23; j++)
				f[dis][j] = f[f[dis][j - 1]][j - 1];
			q.push(dis);
		}
	}
}
inline int lca(int x, int y) {
	if (d[x] > d[y]) swap(x, y);
	for (int i = 23; i >= 0; i--) if (d[f[y][i]] >= d[x]) y = f[y][i];
	if (x == y) return x;
	for (int i = 23; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
int vis[N + 1];
inline void dfs(int u) {
	vis[u] = 1;
	for (int i = head[u]; i; i = edge[i].next) {
		int dis = edge[i].dis;
		if (vis[dis]) continue;
		dfs(dis);
		p[u] += p[dis];
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	bfs();
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &u, &v);
		p[u]++ , p[v]++;
		p[lca(u, v)] -= 2; 
	}
	dfs(1);
	for (int i = 2; i <= n; i++) {
		if (!p[i]) ans += m;
		if (p[i] == 1) ans++; 
	}
	printf("%d\n", ans);
	return 0;
}
上一篇：【网络流】CF708D Incorrect Flow


下一篇：洛谷P4547 [THUWC2017]随机二分图