SPOJ QTREE4 & BZOJ 1095

ACM

lct

SPOJ QTREE4 & BZOJ 1095

题目概括

给定一棵 $n$ 个结点的树，树的边上有权，每个结点有黑白两色，初始时所有的结点都是白的。

有两种操作：

  1. 对一个结点执行反色操作（白变黑，黑变白） ；

  2. 查询树中距离最远的两个白点的距离。

其中$n <= 10^5$，操作数目不超过$5 * 10 ^ 5$.

题目分析

这两道题仔细分析了一下，其实就是一道题—— QTREE4 的边权不定，而 BZOJ 1095 的边权是 1。这道题还可以用边分治搞。

题解

边权LCT维护子树信息，pushup时注意讨论。

对于一个节点维护这样几个值：

  1. 一个multiset维护以该节点为根的子树中所有节点和它的最大，次大距离 (chain)

  2. 一个multiset维护以该节点为根的子树中最远两白点的路径长度 (path)

  3. 以该点为根的辅助树中离在对应的实际的树上最上面节点（其实就是辅助树上最左节点）最远白点距离

  4. 以该点为根的辅助树中离在对应的实际的树上最下面节点（其实就是辅助树上最右节点）最远白点距离

最后该节点为根的子树中的答案就可以通过上面的值合并出来；

在每次反色时更新答案即可。

AC Code

SPOJ QTREE4

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <bits/stdc++.h>
#define RESET(_) memset(_, 0, sizeof(_))
	
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
const int inf = 1e9;
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
	
int top;
int fa[maxn],c[maxn][2];
int val[maxn], mx[maxn], sz[maxn], tag[maxn], sum[maxn], lmx[maxn], rmx[maxn], w[maxn], len[maxn];
multiset <int> chain[maxn], path[maxn]; // 维护链上信息、路径信息 
int q[maxn];
bool rev[maxn];
int n, m, f, t, type, ans;
////边 beg///
struct edge
{
	int to, next, cost;
}edg[maxn << 1];
int fir[maxn], cnt;
void addedge(int f, int t, int w)
{
	edg[++ cnt].next = fir[f];
	fir[f] = cnt;
	edg[cnt].cost = w;
	edg[cnt].to = t;
}
////边 end/// 
int fir_place(multiset <int> &s)
{
	//如果有值的话，返回最后一个 
	return s.size() ? *s.rbegin() : -inf;
}
int sec_place(multiset <int> &s)
{
	//倒数第二个 
	return s.size() > 1 ? *(++ s.rbegin()) : -inf;
}
void init(){
    sz[0] = 0;
	for(int i = 1; i <= n; i ++)
    	sz[i] = 1;
    for(int i = 0; i <= n; i ++)
    	lmx[i] = rmx[i] = mx[i] = -inf;
}
bool isroot(int x)
{
    return c[fa[x]][0]!=x && c[fa[x]][1]!=x;
}
void update(int x)
{
    int l = c[x][0], r = c[x][1];
    sz[x] = sz[l] + sz[r] + 1;
    sum[x] = sum[l] + sum[r] + len[x];
    // sum[x] 表示区间的白点距离和
    int cha = max(w[x], fir_place(chain[x]));
    // cha 表示区间的白点最远距离
    int lmm = max(cha, rmx[l] + len[x]);
    // lmm 表示左子树的最远白点距离
    int rmm = max(cha, lmx[r]);
    // rmm 表示右子树的最远白点距离
    lmx[x] = max(lmx[l], sum[l] + len[x] + rmm);
    // lmx 表示区间左子树连续最大距离和
    rmx[x] = max(rmx[r], sum[r] + lmm);
    // rmx 表示区间右子树连续最大距离和
    mx[x] = max(mx[l], mx[r]);
    // mx 表示区间最大和
    mx[x] = max(mx[x], fir_place(chain[x]) + sec_place(chain[x]));
    // 可能在区间最远和次远距离上
    mx[x] = max(mx[x], fir_place(path[x]));
    //可能在最长路径上
    mx[x] = max(mx[x], max(rmx[l] + len[x] + rmm, lmx[r] + lmm));
    //可能跨区间，max（本身，max（左子树右连续 + 自己 + 右子树最远白点距离，右子树左连续 + 左子树最远白点距离））?(为什么第三个参数少了自己？因为右子树左连续已经包括自己了)
    if(w[x] == 0) mx[x] = max(mx[x], max(fir_place(chain[x]), 0));
    // 如果自己就是白点，就只需要问最远点和自己的距离
}
void pushdown(int x)
{
    int l=c[x][0],r=c[x][1];
    if(rev[x])
    {
        rev[x]^=1;rev[l]^=1;rev[r]^=1;
        swap(c[x][0],c[x][1]);
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],l,r;
    l=(c[y][1]==x);r=l^1;
    if(!isroot(y))c[z][c[z][1]==y]=x;
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
    c[y][l]=c[x][r];c[x][r]=y;
    update(y);update(x);
}
void splay(int x)
{
    top = 0;
    q[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])
        q[++top]=fa[i];
    while(top)pushdown(q[top--]);
    while(!isroot(x))
    {
        int y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if(c[y][0]==x^c[z][0]==y)rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x)
{
    for(int i = 0; x; i = x, x = fa[x])
    {
    	splay(x);
    	if(c[x][1]) chain[x].insert(lmx[c[x][1]]), path[x].insert(mx[c[x][1]]);
    	if(i) chain[x].erase(chain[x].find(lmx[i])), path[x].erase(path[x].find(mx[i]));
		c[x][1] = i;
		update(x);
	}
}
void makeroot(int x)
{
    access(x);splay(x);rev[x] ^= 1;
}
void link(int x,int y)
{
    makeroot(x);fa[x] = y;
	splay(x);
}
	
void cut(int x, int y)
{
	makeroot(x);
	access(y);
	splay(y);
    c[y][0] = fa[c[y][0]] = 0;
    update(y);
}
	
int find(int x){
    access(x);splay(x);
    while(c[x][0]) x = c[x][0];
    return x;
}
	
void modify(int x)
{
    access(x);
    splay(x);
    w[x] = (w[x] == 0 ? -inf : 0);
    update(x);
    ans = mx[x];
}
	
void dfs(int x)
{
	int v;
	for(int i = fir[x]; i; i = edg[i].next)
	{
		v = edg[i].to;
		if(fa[x] != v)
		{
			fa[v] = x;
			len[v] = edg[i].cost;
			dfs(v);
			chain[x].insert(lmx[v]);
			path[x].insert(mx[v]);
		}
	}
	update(x);
}
	
int main()
{
	char op[2];
	scan_d(n);
	init();
	cnt = 0;
	for(int i = 1; i < n; i ++)
	{
		scan_d(f);
		scan_d(t);
		scan_d(type);
		addedge(f, t, type);
		addedge(t, f, type);
	}
	dfs(1);
	ans = mx[1];
	scan_d(m);
	while(m --)
	{
		scanf("%s", op);
		if(op[0] == 'A')
		{
			if(ans < 0) puts("They have disappeared.");
			else printf("%d\n", ans);
		}
		else scanf("%d", &f), modify(f);
	}
	return 0;
}

BZOJ 1095

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
201
202
203
204
205
206
207
208
#include <bits/stdc++.h>
#define RESET(_) memset(_, 0, sizeof(_))
	
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
const int inf = 1e9;
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
	
int top;
int fa[maxn],c[maxn][2];
int val[maxn], mx[maxn], sz[maxn], tag[maxn], sum[maxn], lmx[maxn], rmx[maxn], w[maxn], len[maxn];
multiset <int> chain[maxn], path[maxn]; // 维护链上信息、路径信息 
int q[maxn];
bool rev[maxn];
int n, m, f, t, type, ans;
////边 beg///
struct edge
{
	int to, next;
}edg[maxn << 1];
int fir[maxn], cnt;
void addedge(int f, int t, int w = 1)
{
	edg[++ cnt].next = fir[f];
	fir[f] = cnt;
	//edg[cnt].cost = w;
	edg[cnt].to = t;
}
////边 end/// 
int fir_place(multiset <int> &s)
{
	//如果有值的话，返回最后一个 
	return s.size() ? *s.rbegin() : -inf;
}
int sec_place(multiset <int> &s)
{
	//倒数第二个 
	return s.size() > 1 ? *(++ s.rbegin()) : -inf;
}
void init(){
    sz[0] = 0;
	for(int i = 1; i <= n; i ++)
    	sz[i] = 1;
    for(int i = 0; i <= n; i ++)
    	lmx[i] = rmx[i] = mx[i] = -inf;
}
bool isroot(int x)
{
    return c[fa[x]][0]!=x && c[fa[x]][1]!=x;
}
void update(int x)
{
    int l = c[x][0], r = c[x][1];
    sz[x] = sz[l] + sz[r] + 1;
    sum[x] = sum[l] + sum[r] + len[x];
    int cha = max(w[x], fir_place(chain[x]));
    int lmm = max(cha, rmx[l] + len[x]);
    int rmm = max(cha, lmx[r]);
    lmx[x] = max(lmx[l], sum[l] + len[x] + rmm);
    rmx[x] = max(rmx[r], sum[r] + lmm);
    mx[x] = max(mx[l], mx[r]);
    mx[x] = max(mx[x], fir_place(chain[x]) + sec_place(chain[x]));
    mx[x] = max(mx[x], fir_place(path[x]));
    mx[x] = max(mx[x], max(rmx[l] + len[x] + rmm, lmx[r] + lmm));
    if(w[x] == 0) mx[x] = max(mx[x], max(fir_place(chain[x]), 0));
}
void pushdown(int x)
{
    int l=c[x][0],r=c[x][1];
    if(rev[x])
    {
        rev[x]^=1;rev[l]^=1;rev[r]^=1;
        swap(c[x][0],c[x][1]);
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],l,r;
    l=(c[y][1]==x);r=l^1;
    if(!isroot(y))c[z][c[z][1]==y]=x;
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
    c[y][l]=c[x][r];c[x][r]=y;
    update(y);update(x);
}
void splay(int x)
{
    top = 0;
    q[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])
        q[++top]=fa[i];
    while(top)pushdown(q[top--]);
    while(!isroot(x))
    {
        int y=fa[x],z=fa[y];
        if(!isroot(y))
        {
            if(c[y][0]==x^c[z][0]==y)rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x)
{
    for(int i = 0; x; i = x, x = fa[x])
    {
    	splay(x);
    	if(c[x][1]) chain[x].insert(lmx[c[x][1]]), path[x].insert(mx[c[x][1]]);
    	if(i) chain[x].erase(chain[x].find(lmx[i])), path[x].erase(path[x].find(mx[i]));
		c[x][1] = i;
		update(x);
	}
}
void makeroot(int x)
{
    access(x);splay(x);rev[x] ^= 1;
}
void link(int x,int y)
{
    makeroot(x);fa[x] = y;
	splay(x);
}
	
void cut(int x, int y)
{
	makeroot(x);
	access(y);
	splay(y);
    c[y][0] = fa[c[y][0]] = 0;
    update(y);
}
	
int find(int x){
    access(x);splay(x);
    while(c[x][0]) x = c[x][0];
    return x;
}
	
void modify(int x)
{
    access(x);
    splay(x);
    w[x] = (w[x] == 0 ? -inf : 0);
    update(x);
    ans = mx[x];
}
	
void dfs(int x)
{
	int v;
	for(int i = fir[x]; i; i = edg[i].next)
	{
		v = edg[i].to;
		if(fa[x] != v)
		{
			fa[v] = x;
			len[v] = 1;
			dfs(v);
			chain[x].insert(lmx[v]);
			path[x].insert(mx[v]);
		}
	}
	update(x);
}
	
int main()
{
	char op[2];
	scan_d(n);
	init();
	cnt = 0;
	for(int i = 1; i < n; i ++)
	{
		scan_d(f);
		scan_d(t);
		addedge(f, t);
		addedge(t, f);
	}
	dfs(1);
	ans = mx[1];
	scan_d(m);
	while(m --)
	{
		scanf("%s", op);
		if(op[0] == 'G')
		{
			if(ans < 0) puts("-1");
			else printf("%d\n", ans);
		}
		else scanf("%d", &f), modify(f);
	}
	return 0;
}

本文标题:SPOJ QTREE4 & BZOJ 1095

文章作者:Babydragon

发布时间:2018-08-23, 23:59:31

最后更新:2018-08-24, 00:00:08

原始链接:http://baolintian.github.io/2018/08/23/SPOJ-QTREE4-BZOJ-1095/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. SPOJ QTREE4 & BZOJ 1095
    1. 1.1. 题目概括
    2. 1.2. 题目分析
    3. 1.3. 题解
    4. 1.4. AC Code
      1. 1.4.1. SPOJ QTREE4
      2. 1.4.2. BZOJ 1095
{{ live2d() }}