HDU 5756 Boss Bo【主席树+DFS序】

ACM_数据结构

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5756

题意：

给定一棵$n$个结点的树，以$1$为根节点，$Q$个询问，每个询问中给定序列，若序列中存在元素是树中的结点那么这结点就是坏点，求所有好点与给定的点$P$之间的距离和、最大距离、最小距离。
数据范围：$P, N,K \le 50000, Q \le 100000, \sum{K} \le 200000$

分析：

过程分两个部分：

  1. 预处理出每个点到其他点的距离。首先考虑1号根节点，其他点到$1$号点的最短距离即为其深度减一，这个$dfs$一遍即可求出。由于每个树边权值均为1，我们利用每到一个结点，其子树中的点距离他的距离减一，非子树点距离加一这个性质，子树可以通过$dfs$序获得，再次$dfs$整棵树，过程中每到一个结点就相当于在父节点的线段树基础上进行区间加减操作，这样最终我们得到一个有$n$个根的主席树，每个结点维护区间和、最大值和最小值。
  2. 接下来处理询问。利用一个点是坏点，那么他的子树中的所有结点都是坏点这一性质，$a$中每个元素都对应一个连续区间的坏点，这样我们对坏点取个并集，补集即为好点，从头扫一遍便能获得答案。

这道题卡常，要使用静态标记。

代码：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
/*************************************************************************
    > File Name: 5756.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com
    > Created Time: 2016/9/28 16:26:35
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;//[]
typedef long long ll;
const int maxn =  2e5+ 5, maxm = 30 * maxn + 5, maxq = 2e5 + 5, oo = 0x3f3f3f3f;
typedef pair<int, int>pi;
pi pa[maxq];
int lson[maxm], rson[maxm];
struct EDGE{
	int to, next;
}edge[maxn];
int tot, num;
int b[maxn];
int head[maxn];
ll sum[maxm];
int maxx[maxm], minn[maxm];
ll lazy[maxm];
int rt[maxn];
int n;
int dfn;
int depth[maxn], st[maxn], ed[maxn];
void init()
{
	num = 0;
	tot = 0;
	dfn = 0;
	memset(head, -1, sizeof(head));
}
void addedge(int from, int to)
{
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}
void push_up(int i, int l, int r)
{
	sum[i] = sum[lson[i]] + sum[rson[i]] + (r - l + 1) * 1ll * lazy[i];
	minn[i] = min(minn[lson[i]], minn[rson[i]]) + lazy[i];
	maxx[i] = max(maxx[lson[i]], maxx[rson[i]]) + lazy[i];
}
int build(int l, int r)
{
    int root = ++dfn;
	lazy[root] = 0;
	int mid = l + r >> 1;
    if(l == r){
		sum[root] = maxx[root] = minn[root] = depth[b[l]] - 1;
		lson[root] = rson[root] = 0;
		return root;
	}
    lson[root] = build(l, mid);
    rson[root] = build(mid + 1, r);
	push_up(root, l, r);
    return root;
}
int update(int root, int l, int r, int L, int R, int x)
{
	int newroot = ++dfn;
	sum[newroot] = sum[root];
	lazy[newroot] = lazy[root];
	maxx[newroot] = maxx[root];
	minn[newroot] = minn[root];
    if(L == l && R == r){
        lson[newroot] = lson[root];
        rson[newroot] = rson[root];
		lazy[newroot] += x;
		sum[newroot] += x * 1ll * (r - l + 1);
		maxx[newroot] += x;
		minn[newroot] += x;
		return newroot;
	}
	int mid = l + r >> 1;
    if(R <= mid){
        lson[newroot] = update(lson[root], l, mid, L, R, x);//有变动，重新建立
        rson[newroot] = rson[root];//右边不变
    }else if(L > mid){
        rson[newroot] = update(rson[root], mid + 1, r, L, R, x);//有变动，重新建立
        lson[newroot] = lson[root];//左边不变
    }else{
		lson[newroot] = update(lson[root], l, mid, L, mid, x);
        rson[newroot] = update(rson[root], mid + 1, r, mid + 1, R, x);//有变动，重新建立
	}
	push_up(newroot, l, r);
	return newroot;
}
ll query(int L, int R, int l, int r, int i, int id)
{
	if(L == l && r == R){
		if(id == 1) return sum[i];
		else if(id == 2) return minn[i];
		else return maxx[i];
	}
	int mid = l + r >> 1;
	if(R <= mid){
		ll tmp = query(L, R, l, mid, lson[i], id);
		if(id == 1) return tmp + (R - L + 1) * 1ll * lazy[i];
		return tmp + lazy[i];
	}
	else if(L > mid){
		ll tmp = query(L, R, mid + 1, r, rson[i], id);
		if(id == 1) return tmp + (R - L + 1) * 1ll * lazy[i];
		return tmp + lazy[i];
	}else{
		ll tmp1 = query(L, mid, l, mid, lson[i], id);
		ll tmp2 = query(mid + 1, R, mid + 1, r, rson[i], id);
		if(id == 1) return tmp1 + tmp2 + (R - L + 1) * 1ll * lazy[i];
		else if(id == 2) return min(tmp1, tmp2) + lazy[i];
		return max(tmp1, tmp2) + lazy[i];
	}
}
void dfs(int u, int pa, int deep)
{
	depth[u] = deep;
	st[u] = ++num;
	b[num] = u;
	for(int i = head[u]; i != -1; i = edge[i].next){
		int v = edge[i].to;
		if(v == pa) continue;
		dfs(v, u, deep + 1);
	}
	ed[u] = num;
}
void dfs1(int u, int pa)
{
	for(int i = head[u]; i != -1; i = edge[i].next){
		int v = edge[i].to;
		if(v == pa) continue;
		rt[v] = update(rt[u], 1, n, st[v], ed[v], -1);
		if(st[v] > 1) rt[v] = update(rt[v], 1, n, 1, st[v] - 1, 1);
		if(ed[v] < n) rt[v] = update(rt[v], 1, n, ed[v] + 1, n, 1);
		dfs1(v, u);
	}
}
int main (void)
{
    //freopen("1005.in", "r", stdin);
   // freopen("my_out.txt", "w", stdout);
	int q;
	while(~scanf("%d%d", &n, &q)){
		init();
		int u, v;
		int a;
		for(int i = 0; i < n - 1; i++){
			scanf("%d%d", &u, &v);
			addedge(u, v);
			addedge(v, u);
		}
		dfs(1, 1, 1);
		rt[1] = build(1, n);
		dfs1(1, 1);
		ll ans = 0;
        for(int i = 0; i < q; ++i){
			int k, p, t;scanf("%d%d%d", &k, &p, &t);
			p = (p + ans) % n + 1;
			bool flag = true;
			int totp = 0;
			for(int j = 0; j < k; ++j){
				scanf("%d", &a);
				if(a > n) continue;
				pa[totp++] = pi(st[a], ed[a]);
				if(a == 1) flag = false;
			}
			if(!flag){
				puts("-1");
				ans = 0;
				continue;
			}
			pa[totp++] = pi(n + 1, n + 1);
			sort(pa, pa + totp);
			if(t == 1) ans = 0;
			else if(t == 2) ans = oo;
			else if(t == 3) ans = -oo;
			int l = 1;
			ll tmp;
			for(int j = 0; j < totp; j++){
				if(l < pa[j].first){
					tmp = query(l, pa[j].first - 1, 1, n, rt[p], t);
					if(t == 1) ans += tmp;
					else if(t == 2) ans = min(ans, tmp);
					else ans = max(ans, tmp);
				}
				l = max(l, pa[j].second + 1);
			}
			printf("%lld\n", ans);
		}
	}
}
文章目录
  1. 1. 题目链接：
  2. 2. 题意：
  3. 3. 分析：
  4. 4. 代码：