TJOI2016树

TJOI
倍增, 并查集, 线段树

TJOI2016 树

题目大意：

给定一颗有根树（根为1），有以下两种操作：

  1. 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）
  2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）

题解：

我们发现，每标记一个节点，受到影响的就只有以这个节点为根的子树。

于是很容易想到，用dfs序来表示一个子树。

每加一个标记，就把对应的子树中的信息全部更新一遍。

我们可以在节点上记录，最近的一个打了标记的祖先的深度。

这样就可以用一个简单的线段树来更新与查询了。

知道了深度，利用倍增跳上去即可。

另外，本题还有一种更加厉害的解法。

我们发现，标记是不可撤回的，因而目标节点深度只会越来越深。

考虑离线地写这道题。

我们把所有操作都一口气进行，再一个一个撤回。

这样目标节点只会越来越浅。

我们可以利用并查集，把中间无用的路径压缩掉。（标记撤回后，答案往上升，中间的路径信息就没用了）

综上，这道题的复杂度可以做到$O(n+m)$。（并查集的复杂度忽略掉）

Code:

这里只给出线段树的代码

我不会告诉你我是因为懒得写第二种写法才不放代码的

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
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=100005;
int n,q,tot_edge,head[N];
struct Edge{
	int to,nxt;
}edge[N<<1];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
int tot_node,L[N],R[N],dep[N],fa[N][21];
void dfs(int p,int f,int d){
	L[p]=++tot_node;
	dep[p]=d,fa[p][0]=f;
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		dfs(to,p,d+1);
	}
	R[p]=tot_node;
}
struct Segment_Tree{
	struct node{
		int L,R,mx,flag;
	}tree[N<<2];
	void build(int L,int R,int p){
		tree[p].L=L,tree[p].R=R,tree[p].mx=0;
		tree[p].flag=0;
		if(L==R)return;
		int mid=L+R>>1;
		build(L,mid,p<<1);
		build(mid+1,R,p<<1|1);
	}
	void up(int p){
		tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx);
	}
	void down(int p){
		if(tree[p].flag){
			tree[p<<1].mx=max(tree[p<<1].mx,tree[p].flag);
			tree[p<<1|1].mx=max(tree[p<<1|1].mx,tree[p].flag);
			tree[p<<1].flag=max(tree[p<<1].flag,tree[p].flag);
			tree[p<<1|1].flag=max(tree[p<<1|1].flag,tree[p].flag);
			tree[p].flag=0;
		}
	}
	void update(int L,int R,int v,int p){
		if(tree[p].L==L&&tree[p].R==R){
			tree[p].flag=max(tree[p].flag,v);
			tree[p].mx=max(tree[p].mx,v);
			return;
		}
		down(p);
		int mid=tree[p].L+tree[p].R>>1;
		if(R<=mid)update(L,R,v,p<<1);
		else if(L>mid)update(L,R,v,p<<1|1);
		else update(L,mid,v,p<<1),update(mid+1,R,v,p<<1|1);
		up(p);
	}
	int query(int x,int p){
		if(tree[p].L==tree[p].R){
			return tree[p].mx;
		}
		down(p);
		int mid=tree[p].L+tree[p].R>>1;
		if(x<=mid)return query(x,p<<1);
		else return query(x,p<<1|1);
	}
}T;
void up(int&p,int step){
	for(int i=0;i<=20;i++){
		if(step&(1<<i))p=fa[p][i];
	}
}
int main(){
	memset(head,-1,sizeof(head));
	Rd(n),Rd(q);
	for(int i=1,a,b;i<n;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);
	}
	dfs(1,0,0);
	for(int j=1;j<=20;j++){
		for(int i=1;i<=n;i++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	T.build(1,n,1);
	for(int i=1;i<=q;i++){
		char op[2];
		int p;
		scanf("%s %d",op,&p);
		if(op[0]=='Q'){
			int ans_dep=T.query(L[p],1);
			up(p,dep[p]-ans_dep);
			printf("%d\n",p);
		}else{
			T.update(L[p],R[p],dep[p],1);
		}
	}
	return 0;
}
分享到 评论