mydcwfy's Blog

UOJ715 【北大集训 2021】小明的树

Posted on
Symbols count in article: 2.6k Reading time ≈ 6 mins.

题意：给定一棵 $n$ 个点的以 1 为根的树和一个删除序列，每次删除一个 $[2, n]$ 之类的点，当对于任意一个删除的点都有其所有子树的点都被删除时，答案加上删除点的连通块个数。一棵树的价值为最后删除完的答案。动态修改树，删除一条边，加上一条边，保证还是树。实时维护答案。$n, q\leq 5\times 10 ^ 5$。

诈骗结论：树的连通块个数是点数减去边数。容易发现这个结论是显然的，不过在统计连通块个数的时候非常有用。

容易发现这个条件其实就是删除的点的连通块个数恰好为 1。考虑对时间轴维护连通块个数，然后对于所有未删点的连通块个数为 1 的时间点，维护删除的点的连通块个数并求和。容易发现这个在树动态的时候也很好维护，直接区间加减即可。

最后一个问题就是如何维护连通块个数为 1 的时间点的删除点的连通块个数和。容易发现连通块个数最少是 1，于是可以用线段树维护区间的最小值和最小值对应位置的权值和。注意因为要区间加权值，还需要维护区间最小值个数。

注意开 long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct Segment_Tree {
	struct Node {
		int l, r;
		int mn, cnt, mntag, valtag;
		LL val;
	} tr[N << 2];
	
	void pushup(int x)
	{
		auto &rt = tr[x], &nl = tr[x << 1], &nr = tr[x << 1 | 1];
		if (nl.mn < nr.mn) rt.mn = nl.mn, rt.val = nl.val, rt.cnt = nl.cnt;
		else if (nl.mn > nr.mn) rt.mn = nr.mn, rt.val = nr.val, rt.cnt = nr.cnt;
		else rt.mn = nl.mn, rt.val = nl.val + nr.val, rt.cnt = nl.cnt + nr.cnt;
	}
	
	void build(int x, int l, int r)
	{
		tr[x] = {l, r, 0, r - l + 1};
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
	}
	
	void update_key(int x, int c) { tr[x].mn += c, tr[x].mntag += c; }
	
	void update_val(int x, int c) { tr[x].val += (LL) c * tr[x].cnt, tr[x].valtag += c; }
	
	void pushdown(int x)
	{
		if (tr[x].mntag) update_key(x << 1, tr[x].mntag), update_key(x << 1 | 1, tr[x].mntag), tr[x].mntag = 0;
		if (tr[x].valtag) update_val(x << 1, tr[x].valtag), update_val(x << 1 | 1, tr[x].valtag), tr[x].valtag = 0;
	}
	
	void modify_key(int x, int l, int r, int c)
	{
		// if (x == 1) std::cout << "Modify Key " << l << ' ' << r << ' ' << c << '\n';
		if (tr[x].l > r || tr[x].r < l) return;
		if (tr[x].l >= l && tr[x].r <= r) return update_key(x, c);
		pushdown(x);
		modify_key(x << 1, l, r, c), modify_key(x << 1 | 1, l, r, c);
		pushup(x);
	}
	
	void modify_val(int x, int l, int r, int c)
	{
		// if (x == 1) std::cout << "Modify Val " << l << ' ' << r << ' ' << c << '\n';
		if (tr[x].l > r || tr[x].r < l) return;
		if (tr[x].l >= l && tr[x].r <= r) return update_val(x, c);
		pushdown(x);
		modify_val(x << 1, l, r, c), modify_val(x << 1 | 1, l, r, c);
		pushup(x);
	}
} seg;

void link(int x, int y)
{
	seg.modify_key(1, 1, std::min(nw[x], nw[y]) - 1, -1);
	seg.modify_val(1, std::max(nw[x], nw[y]), n - 1, -1);
}

void cut(int x, int y)
{
	seg.modify_key(1, 1, std::min(nw[x], nw[y]) - 1, 1);
	seg.modify_val(1, std::max(nw[x], nw[y]), n - 1, 1);
}

void answer() {
	if (seg.tr[1].mn == 1) printf("%lld\n", seg.tr[1].val);
	else puts("0");
}