QTREE系列
发表更新ICPC/CCPC / Exercises8 分钟读完 (大约1253个字)

QTREE系列

Query on a tree.

QTREE 1

题意简述：给定一棵 $n$ 个点的树，要求支持两种操作：改动某条边的权值、询问点 $a$ 到点 $b$ 路径上的最大边权。

题解：树链剖分+线段树。注意一个坑：由于我们要将边权下放到点权，在查询 $a,b$ 时，不能将 $\text{lca}(a,b)$ 计入答案。

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
#include<bits/stdc++.h>

using namespace std;

const int N = 10005;

int n, a[N], which[N];

struct Edge{
	int nxt, to, dis, id;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to, int dis, int id){
	edge[++edgeNum] = (Edge){head[from], to, dis, id};
	head[from] = edgeNum;
}

int fa[N], dep[N], son[N], sz[N];
void dfs(int x, int f, int depth){
	fa[x] = f; dep[x] = depth; sz[x] = 1; son[x] = 0;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == f)	continue;
		dfs(edge[i].to, x, depth + 1);
		sz[x] += sz[edge[i].to];
		if(!son[x] || sz[edge[i].to] > sz[son[x]])	son[x] = edge[i].to;
		which[edge[i].id] = edge[i].to;
		a[edge[i].to] = edge[i].dis;
	}
}
int top[N], st[N], ed[N], dfsClock, func[N];
void dfs(int x, int tp){
	st[x] = ++dfsClock; func[dfsClock] = x; top[x] = tp;
	if(son[x])	dfs(son[x], tp);
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == fa[x] || edge[i].to == son[x])	continue;
		dfs(edge[i].to, edge[i].to);
	}
	ed[x] = dfsClock;
}

#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
struct segTree{
	int l, r, mx;
}tr[N<<2];
inline void pushup(int id){
	tr[id].mx = max(tr[lid].mx, tr[rid].mx);
}
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r;
	tr[id].mx = 0;
	if(tr[id].l == tr[id].r){
		tr[id].mx = a[func[l]];
		return;
	}
	build(lid, l, mid), build(rid, mid+1, r);
	pushup(id);
}
void modify(int id, int pos, int val){
	if(tr[id].l == tr[id].r){
		tr[id].mx = val;
		return;
	}
	if(pos <= mid)	modify(lid, pos, val);
	else	modify(rid, pos, val);
	pushup(id);
}
int query(int id, int l, int r){
	if(tr[id].l == l && tr[id].r == r)	return tr[id].mx;
	if(r <= mid)	return query(lid, l, r);
	else if(l > mid)	return query(rid, l, r);
	else	return max(query(lid, l, mid), query(rid, mid+1, r));
}

inline void modifyVertex(int u, int val){
	modify(1, st[u], val);
}
inline int queryPath(int u, int v){
	int res = 0;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])	swap(u, v);
		res = max(res, query(1, st[top[u]], st[u]));
		u = fa[top[u]];
	}
	if(dep[u] < dep[v])	swap(u, v);
	if(st[v] + 1 <= st[u])
		res = max(res, query(1, st[v]+1, st[u]));
	return res;
}

inline void init(){
	for(int i = 1; i <= n; i++){
		head[i] = a[i] = which[i] = 0;
		son[i] = fa[i] = dep[i] = sz[i] = 0;
		top[i] = st[i] = ed[i] = func[i] = 0;
	}
	edgeNum = dfsClock = 0;
}

int main(){
	int T; for(scanf("%d", &T); T; T--){
		scanf("%d", &n);
		init();
		for(int i = 1; i < n; i++){
			int u, v, w; scanf("%d%d%d", &u, &v, &w);
			addEdge(u, v, w, i), addEdge(v, u, w, i);
		}
		dfs(1, 0, 1);
		dfs(1, 1);
		build(1, 1, n);
		char opt[10];
		while(1){
			scanf("%s", opt);
			if(opt[0] == 'D')	break;
			int x, y; scanf("%d%d", &x, &y);
			if(opt[0] == 'C')	modifyVertex(which[x], y);
			else	printf("%d\n", queryPath(x, y));
		}
	}
	return 0;
}

QTREE2

题意简述：给定一棵 $n$ 个点的树，要求支持两种操作：询问 $a$ 到 $b$ 的距离、询问从 $a$ 到 $b$ 的路径上的第 $k$ 个点的编号。

题解：倍增。距离就是 $\text{dis}_a+\text{dis}_b-2\text{dis}_{\text{lca}(a,b)}$，而后一个询问可以转化成求某个点的第 $k$ 个父节点，倍增自然可以搞定。

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
#include<bits/stdc++.h>

using namespace std;

const int N = 10005;

int n;

struct Edge{
	int nxt, to, dis;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to, int dis){
	edge[++edgeNum] = (Edge){head[from], to, dis};
	head[from] = edgeNum;
}

int fa[N][25], dep[N], dis[N];
void dfs(int x, int f, int depth){
	dep[x] = depth, fa[x][0] = f;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == f)	continue;
		dis[edge[i].to] = dis[x] + edge[i].dis;
		dfs(edge[i].to, x, depth+1);
	}
}
void init(){
	for(int j = 1; (1 << j) <= n; j++)
		for(int i = 1; i <= n; i++)
			if(fa[i][j-1])
				fa[i][j] = fa[fa[i][j-1]][j-1];
}
inline int lca(int x, int y){
	if(dep[x] < dep[y])	swap(x, y);
	for(int i = 20; i >= 0; i--)
		if(dep[x] - (1 << i) >= dep[y])
			x = fa[x][i];
	if(x == y)	return x;
	for(int i = 20; i >= 0; i--)
		if(fa[x][i] && fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
inline int getFa(int x, int k){
	for(int i = 20; i >= 0; i--)
		if(k >= (1<<i))
			x = fa[x][i], k -= (1<<i);
	return x;
}

int main(){
	int T; for(scanf("%d", &T); T; T--){
		scanf("%d", &n);
		edgeNum = 0;
		for(int i = 1; i <= n; i++){
			head[i] = dep[i] = dis[i] = 0;
			for(int j = 0; j <= 20; j++)	fa[i][j] = 0;
		}
		for(int i = 1; i < n; i++){
			int u, v, w; scanf("%d%d%d", &u, &v, &w);
			addEdge(u, v, w), addEdge(v, u, w);
		}
		dfs(1, 0, 1);
		init();
		char opt[10];
		while(1){
			scanf("%s", opt);
			if(opt[1] == 'O')	break;
			int a, b; scanf("%d%d", &a, &b);
			int l = lca(a, b);
			if(opt[1] == 'I')	printf("%d\n", dis[a] + dis[b] - 2 * dis[l]);
			else{
				int k; scanf("%d", &k);
				if(k <= dep[a] - dep[l] + 1)	printf("%d\n", getFa(a, k-1));
				else	printf("%d\n", getFa(b, dep[a] + dep[b] - 2 * dep[l] + 1 - k));
			}
		}
	}
	return 0;
}

QTREE3

题意简述：给定一棵 $n$ 个点的树，节点有黑白两色，初始全白。要求支持两种操作：改变某点的颜色、询问从点 $1$ 到某点的路径上的第一个黑点编号。

题解：树链剖分+set。一个 set 存储一个重链中的所有黑点（的 $\text{dfs}$ 序）。

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
#include<bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, q;
bool a[N];

struct Edge{
	int nxt, to;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to){
	edge[++edgeNum] = (Edge){head[from], to};
	head[from] = edgeNum;
}

int fa[N], dep[N], son[N], sz[N];
void dfs(int x, int f, int depth){
	fa[x] = f; dep[x] = depth; sz[x] = 1; son[x] = 0;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == f)	continue;
		dfs(edge[i].to, x, depth + 1);
		sz[x] += sz[edge[i].to];
		if(!son[x] || sz[edge[i].to] > sz[son[x]])	son[x] = edge[i].to;
	}
}
int top[N], st[N], ed[N], dfsClock, func[N];
void dfs(int x, int tp){
	st[x] = ++dfsClock; func[dfsClock] = x; top[x] = tp;
	if(son[x])	dfs(son[x], tp);
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].to == fa[x] || edge[i].to == son[x])	continue;
		dfs(edge[i].to, edge[i].to);
	}
	ed[x] = dfsClock;
}

set<int> s[N];
inline void reverseVertex(int x){
	if(a[x])	s[top[x]].erase(st[x]);
	else	s[top[x]].insert(st[x]);
}
inline int queryPath(int x){
	int res = 1e9;
	while(top[x] != 1){
		if(!s[top[x]].empty() && *s[top[x]].begin() <= st[x])
			res = min(res, *s[top[x]].begin());
		x = fa[top[x]];
	}
	if(!s[1].empty() && *s[1].begin() <= st[x])
		res = min(res, *s[1].begin());
	return res;
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 1; i < n; i++){
		int u, v; scanf("%d%d", &u, &v);
		addEdge(u, v), addEdge(v, u);
	}
	dfs(1, 0, 1);
	dfs(1, 1);
	while(q--){
		int opt, x; scanf("%d%d", &opt, &x);
		if(opt == 0)	reverseVertex(x), a[x] = !a[x];
		else{
			int dfn = queryPath(x);
			if(dfn == 1e9)	puts("-1");
			else	printf("%d\n", func[dfn]);
		}
	}
	return 0;
}

QTREE系列

http://xyfjason.github.io/blog-xcpc/2020/12/14/QTREE系列/

作者

xyfJASON

发布于

2020-12-14

更新于

2021-02-25

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×