HeinzHuang

Eudaimonia

0%

Query on a tree IV(SPOJ - QTREE4)

Posted on Edited on In

题目描述：

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3…,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.

All the nodes are white initially.

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

  • C a : change the color of node a.(from black to white or from white to black)
  • A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

给出一棵n个结点的树，每条边有边权。一开始，每个点都是白色的。 再给出q个询问，每次询问有两种操作：

1.C a 表示改变a结点的颜色，黑变白，白变黑。
2.A 表示询问树上某两个白点（可以是同一个点）间最远距离 注意原题卡常，可以尝试换用clang编译器提交。

思路：

QTree 5 的进化版。。（为甚是这个顺序我也不清楚。。）

主要操作和QTree4的操作差不多，详细内容可见那题题解：Query on a tree V

上一题的思想是在每个点开一个可删堆\(Q1\)，然后利用点分树优化查询与更新，这次其实也差不多只不过它并没有给你确定其中一个点，那么接下来的操作就比较骚有趣了

为了避免多次枚举，我们在每个点上多开一个队列\(Q2\)，存的内容是距离每个儿子上最远的点到自身的距离，听起来有些绕，好好理解一下。。然后每次更新时，只要注意当前的儿子的最远距离（记录在原先的那个队列中）——也就是\(Q1\)的\(Top\)被更新掉时，就要对应的去更新它父亲的\(Q2\)，注意要算上儿子到父亲的距离，为了方便，我的\(Q1\)中存的值就是算上它到父亲的距离的。那么若要找经过该点的最大距离时，就只用在它所对应的\(Q2\)中找出最大的两个值的和即可（注意如果只有一个值的时候，要返回0，因为题意说明可以是同一个点也算）。

所以代码中最关键的两点就是对于这三种队列的更新了！仔细理解。

最后就是把每个点的最大值存在最后一个队列\(A\)中，同理每次一个点的\(Q2\)中的最大两值和改变时，都要在\(A\)中进行对应的更新(删除旧值，加入新值)，那么最终查询答案只要返回\(A\)的\(Top\)即可，至于没有白点的判断，只要维护一个\(tot\)，计数白点数量，不必多说！

还有一个需要说的就是点分树的存法，由于这题时限，不能用常规\(log\)求\(LCA\)来算距离，可以全部预处理出来存一个正向表（或\(vector\)）中。存每个儿子的每个父亲以及距离，这些均可以在一个\(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
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
#include<cstdio>
#include<cstring>
#include<queue>
#define FOR(i,l,r) for(register int i=l,END=r;i<=END;i++)
#define DOR(i,r,l) for(register int i=r,END=l;i>=END;i--)
#define loop(i,n) for(register int i=0,END=n;i<END;i++)
#define mms(a,x) memset(a,x,sizeof a)
#define sf scanf
#define pf printf
using namespace std;
const int N=1e5+5,INF=1e9;
int n;
struct Graph{
	int tot,to[N*20],nxt[N*20],len[N*20],head[N];
	void add(int x,int y,int z){tot++;to[tot]=y;nxt[tot]=head[x];len[tot]=z;head[x]=tot;}
	void clear(){mms(head,-1);tot=0;}
	#define EOR(A,i,x) for(register int i=A.head[x];i!=-1;i=A.nxt[i])
}G,G2;//原树和点分树的路径 

struct Heap{//可删堆 
	priority_queue<int>Q,del;
	void Push(int x){if(x!=-INF)Q.push(x);}
	void Del(int x){if(x!=-INF)del.push(x);}
	void upd(){while(!del.empty()&&Q.top()==del.top())Q.pop(),del.pop();}
	int Size(){return Q.size()-del.size();}
	int Top(){upd();if(Q.empty())return -INF;return Q.top();}
	int Sum2(){
		upd();int siz=Size();
		if(!siz)return -INF;
		if(siz==1)return 0;
		int mx1=Top();Q.pop();
		int mx2=Top();Q.push(mx1);
		return max(mx1+mx2,0);
	}
}A,B[N],C[N];//C便是题解中的Q1,B便是题解中的Q2

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

struct DAC_Tree{//点分树 
	bool vis[N];
	int sz[N],mx[N],fa[N];
	int t_sz,center;
	void get_dis(int x,int f,int dis,int center){//预处理上面的G2 
		G2.add(x,center,dis);
		EOR(G,i,x){
			int v=G.to[i];
			if(v==f||vis[v])continue;
			get_dis(v,x,dis+G.len[i],center);
		}
	}
	void get_center(int x,int f){//寻找重心 
		sz[x]=1,mx[x]=0;
		EOR(G,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;
		G2.add(x,x,0);
		EOR(G,i,x){
			int v=G.to[i];
			if(vis[v])continue;
			get_dis(v,x,G.len[i],x);
			center=0,t_sz=sz[v];
			get_center(v,x);
			fa[center]=x;
			DAC(center);
		}
	}
	
	//以下两个函数为本题关键，注意三个队列的更新 
	void insert(int x){//把一个点变白 
		int sum=B[x].Sum2();
		B[x].Push(0);
		int nsum=B[x].Sum2();
		if(nsum!=sum){
			A.Del(sum);
			A.Push(nsum);
		}
		EOR(G2,i,x){
			if(G2.nxt[i]==-1)break;
			int v=G2.to[i],f=G2.to[G2.nxt[i]],dis=G2.len[G2.nxt[i]],tp=C[v].Top();
			C[v].Push(dis);
			int ntp=C[v].Top();
			if(ntp!=tp){
				sum=B[f].Sum2();
				B[f].Del(tp);
				B[f].Push(dis);
				nsum=B[f].Sum2();
				if(nsum!=sum){
					A.Del(sum);
					A.Push(nsum);
				}
			}
		}
	}
	void erase(int x){//把一个点变黑 
		int sum=B[x].Sum2();
		B[x].Del(0);
		int nsum=B[x].Sum2();
		if(nsum!=sum){
			A.Del(sum);
			A.Push(nsum);
		}
		EOR(G2,i,x){
			if(G2.nxt[i]==-1)break;
			int v=G2.to[i],dis=G2.len[G2.nxt[i]],f=G2.to[G2.nxt[i]],tp=C[v].Top();
			C[v].Del(dis);
			int ntp=C[v].Top();
			if(ntp!=tp){
				sum=B[f].Sum2();
				if(tp!=-INF)B[f].Del(tp);
				B[f].Push(C[v].Top());
				nsum=B[f].Sum2();
				if(nsum!=sum){
					A.Del(sum);
					A.Push(nsum);
				}
			}			
		}
	}
	//预处理 
	void init(){
		center=0,t_sz=n;
		get_center(1,0);
		DAC(center);
		FOR(i,1,n)insert(i);
	}
}Tr;

int tot;
int main(){
	G.clear(),G2.clear();
	sf("%d",&n);
	loop(i,n-1){
		int x,y,z;
		sf("%d%d%d",&x,&y,&z);
		G.add(x,y,z),G.add(y,x,z);
	}
	Tr.init();
	int q;tot=n;
	sf("%d",&q);
	while(q--){
		char op[5];
		sf("%s",op);
		if(op[0]=='A'){
			if(!tot)pf("They have disappeared.\n");//无白点 
			else pf("%d\n",A.Top());
		}
		else { 
			int a;sf("%d",&a); 
			col[a]^=1;
			if(col[a]){Tr.erase(a);tot--;}
			else {Tr.insert(a);tot++;}
		}
	}
	return 0;
}