HeinzHuang

Eudaimonia

0%

Query on a tree V（SPOJ - QTREE5）

Posted on Edited on In

题目描述：

You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. We define dist(a, b) as the number of edges on the path from node a to node b.

Each node has a color, white or black. All the nodes are black initially.

We will ask you to perfrom some instructions of the following form:

  • 0 i : change the color of i-th node(from black to white, or from white to black).
  • 1 v : ask for the minimum dist(u, v), node u must be white(u can be equal to v). Obviously, as long as node v is white, the result will always be 0.

给出一棵n结点的树，边权为1，一开始每个点颜色都是黑色。 现有q个询问，每次询问会有两种操作： 1.0 i 改变i的颜色，黑变白，白变黑。 2.1 v 询问与v距离最近的白点，显然，当v颜色为白色时，答案是0。

输入

  • In the first line there is an integer N (N <= 100000)
  • In the next N-1 lines, the i-th line describes the i-th edge: a line with two integers a b denotes an edge between a and b.
  • In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
  • In the next Q lines, each line contains an instruction “0 i” or “1 v”

输出

For each “1 v” operation, print one integer representing its result. If there is no white node in the tree, you should write “-1”.

思路：

这是自己写的第一个动态点分治题。

堆

在每个点上都建立一个可删除堆（手写也可以，像我一样偷懒的话两个系统堆模拟也行，一个记录队列中加入的，一个记录堆中被删除的元素，每次遇到队首相同的元素，就同时弹出即可！）这样每个点都可以（近乎）\(O(1)\)的求出一个点上的答案，不过这样的话，更新的复杂度会直接爆炸！

点分治

动态点分治的用处这时就体现出来了，就只用更新点分治树树根到该点的路径上的所有点即可，复杂度为\(O(logn)\)，然后在询问的时候，同理在这条路径上，枚举每一个点，将该点队列上的最大值再加上该点到询问点上的距离的值求出，一路\(min\)上去最后得到的就是答案，复杂度同样为\(O(logn)\)，枚举该路径只要从当前点开始在点分治树上跳父亲即可

最后就是求两点之间的路径长度，应该不难，用\(LCA\)法即可，\(lca\)可以直接预处理，用跳重链法等都可以，有 

1
dis(x,y)=dep[x]+dep[y]-dep[lca]*2
\(dep\)为该点深度。

代码

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
#include<cstdio>
#include<cstring>
#include<queue>
#define FOR(i,l,r) for(int i=l,END=r;i<=END;i++)
#define DOR(i,r,l) for(int i=r,END=l;i>=END;i--)
#define loop(i,n) for(int i=0,END=n;i<END;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+5;

struct Graph{//正向表 
	int tot,to[N<<1],nxt[N<<1],head[N];
	void add(int x,int y){tot++;to[tot]=y;nxt[tot]=head[x];head[x]=tot;}
	void clear(){mms(head,-1);tot=0;}
	#define EOR(i,x) for(int i=G.head[x];i!=-1;i=G.nxt[i])
}G;

struct Distance_Calculator{//计算两点的路径 
	int sz[N],son[N],fa[N],dep[N],top[N];
	void dfs(int x,int f){
		fa[x]=f,dep[x]=dep[f]+1;
		sz[x]=1,son[x]=0;
		EOR(i,x){
			int v=G.to[i];
			if(v==f)continue;
			dfs(v,x);
			sz[x]+=sz[v];
			if(sz[son[x]]<sz[v])son[x]=v;
//			pf("x:%d son[x]:%d\n",x,son[x]);
		}
	}
	void top_dfs(int x,int f,int tp){
//		pf("x:%d f:%d tp:%d son[x]:%d\n",x,f,tp,son[x]);
		top[x]=tp;
		if(son[x])top_dfs(son[x],x,tp);
		EOR(i,x){
			int v=G.to[i];
			if(v==f||v==son[x])continue;
			top_dfs(v,x,v);
		}
	}
	int LCA(int x,int y){//跳重链 
		while(top[x]!=top[y]){
			if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
			else y=fa[top[y]];
		}
		return dep[y]>dep[x]?x:y;
	}
	int dist(int x,int y){return dep[x]+dep[y]-(dep[LCA(x,y)]<<1);}
	void init(){
		dfs(1,0);
		top_dfs(1,0,1);
	}
}D;

int fa[N];

struct Heap{//可删除堆 
	priority_queue<int,vector<int>,greater<int> >Q,del;
	void Del(int x){del.push(x);}
	void Erase(){while(!del.empty()&&del.top()==Q.top())Q.pop(),del.pop();}
	void Push(int x){Q.push(x);}
	bool Empty(){Erase();return Q.empty();}
	int Top(){Erase();if(Empty())return -1;else return Q.top();}
	
}H[N];

int n;
bool vis[N];
int sz[N],mx[N],center,t_sz;
void get_center(int x,int f){//找重心 
	sz[x]=1,mx[x]=0;
	EOR(i,x){
		int v=G.to[i];
		if(v==f||vis[v])continue;
		get_center(v,x);
		sz[x]+=sz[v];
		mx[x]=max(mx[x],sz[v]);
	}
	mx[x]=max(mx[x],t_sz-sz[x]);
	if(!center||mx[center]>mx[x])center=x;
}
void DAC(int x){//预处理点分树 
	vis[x]=1;
	EOR(i,x){
		int v=G.to[i];
		if(vis[v])continue;
		t_sz=sz[v],center=0;
		get_center(v,x);
		fa[center]=x;//关键 
		DAC(center);
	}
}

bool col[N];//记录颜色 

void insert(int x){
	H[x].Push(0);//加入自己本身 
	for(int i=fa[x];i;i=fa[i]){//暴跳父亲，更新 
		int dis=D.dist(x,i);
		H[i].Push(dis);
	}
}
void erase(int x){
	H[x].Del(0);//删除自己本身 
	for(int i=fa[x];i;i=fa[i]){//暴跳父亲，删除 
		int dis=D.dist(x,i);
		H[i].Del(dis);
	}
}
int Query(int x){//询问 
	int ret=2e9;
	for(int i=x;i;i=fa[i]){
		int dis=D.dist(x,i);
		int dis2=H[i].Top();
		if(dis2==-1)continue;
		ret=min(ret,dis2+dis);
	}
	return ret==2e9?-1:ret;
}
int main(){
	G.clear();
	sf("%d",&n);
	FOR(i,1,n-1){
		int x,y;
		sf("%d%d",&x,&y);
		G.add(x,y);
		G.add(y,x);
	}
	t_sz=n,get_center(1,0);
	DAC(center);
	D.init();
	//以上为预处理 
	int q;
	sf("%d",&q);
	while(q--){
		int op,v;
		sf("%d%d",&op,&v);
		if(!op){
			col[v]^=1;
			if(col[v])insert(v);
			else erase(v);
		}
		else pf("%d\n",Query(v));
	}
	return 0;
}