线段树维护树的直径

ACM

这是一种类型题。

线段树维护树的直径

概述

我们需要快速回答一棵子树的直径，或者去掉一棵树以后形成的最大直径。

一般是写 DFS ，复杂度是 $O(n)$ ，本文将给出 $O(n \log n)$ 的算法。

本文可以解决的问题

在不改变树的长度的时候，询问去掉一些子树以后形成的最大直径。

如果树的边权被改变的话，请用树分治。（2018 年区域赛 青岛）

算法流程

  1. 做出树的 DFS 序，以 DFS 序做出线段树，任意两个点的距离利用离线 LCA 维护。

  2. 每个区间（线段树的结点）维护距离最远的两个端点（直径可以通过端点算出来）。注意初值的选取，一定要保证在区间内选取。

    • 如果区间只有一个结点，最远的两个端点就是区间内唯一一个点；
    • 合并两个区间：左区间有两个直径端点，右区间也有两个直径端点，这四个点中的最远点对，就是新区间的直径。

应用

XDOJ 1380 小萌和小明

$n$ 个点构成的一棵树，给出 $[a, b]$ 和 $[c, d]$ 两个区间，表示点的标号。

求出在这两个区间内各选一点之间的最大距离是多少。也就是 $\max { \text{dis}(i,j) |a\leq i \leq b,c \leq j \leq d }$

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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
#include <bits/stdc++.h>
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) (((_) << 1))
# define DXB(_) (((_) << 1) | 1)
	
# define next __Chtholly__
# define distance __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 100009;
const int maxm = 100009;
const ll inf = 1e18;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
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;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
template <class T>
inline void out_number(T x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
int n, m, cnt, cnt_hld;
int fir[maxn], dfs_time[maxn << 1], deep[maxn], pos[maxn], st2[maxn << 1][21], log_2[maxn << 1];
ll dis[maxn];
	
struct edg
{
	int to, next;
	ll val;
}edg1[maxn << 1];
	
inline void addedge(int f, int t, ll val)
{
	edg1[++ cnt].to = t;
	edg1[cnt].next = fir[f];
	edg1[cnt].val = val;
	fir[f] = cnt;
}
	
void dfs1(int u, int fa, int dep)
{
	pos[u] = ++ cnt_hld;
	dfs_time[cnt_hld] = u;
	deep[u] = dep;
	for(register int i = fir[u], v; i; i = edg1[i].next)
		if((v = edg1[i].to) != fa)
		{
			dis[v] = dis[u] + edg1[i].val;
			dfs1(v, u, dep + 1);
			dfs_time[++ cnt_hld] = u;
		}
}
	
inline void rmqinit()
{
	for(register int i = 1; i <= cnt_hld; ++ i)
		st2[i][0] = dfs_time[i];
	for(register int i = 1; i <= 20; ++ i)
		for(register int j = 1; j + (1 << i) - 1 <= cnt_hld; ++ j)
		{
			if(deep[st2[j][i - 1]] < deep[st2[j + (1 << (i - 1))][i - 1]])
				st2[j][i] = st2[j][i - 1];
			else st2[j][i] = st2[j + (1 << (i - 1))][i - 1];
		}
	log_2[1] = 0;// 必须开两倍 
	for(register int i = 2; i <= cnt_hld; ++ i)
	{
		if((1 << (log_2[i - 1] + 1)) < i) log_2[i] = log_2[i - 1] + 1;
		else log_2[i] = log_2[i - 1]; 
	}
}
	
int RMQ(int x, int y)
{
	int a = log_2[y - x + 1];
	if(deep[st2[x][a]] < deep[st2[y - (1 << a) + 1][a]])
		return st2[x][a];
	return st2[y - (1 << a) + 1][a];
}
	
ll distance(int x, int y)
{
	if(pos[x] > pos[y]) swap(x, y);
	int LCA = RMQ(pos[x], pos[y]);
	return dis[x] + dis[y] - (dis[LCA] << 1);
}
	
int tree[maxn << 2][2];
	
inline void __make(ll &ans, int &s1, int &s2, int v1, int v2)
{
	ans = distance(v1, v2), s1 = v1, s2 = v2;
}
	
inline void __pushup(int &s1, int &s2, int a1, int a2, int b1, int b2)
{
	ll ans = 0; 
	if(ans < distance(a1, a2)) __make(ans, s1, s2, a1, a2);
	if(ans < distance(a1, b1)) __make(ans, s1, s2, a1, b1);
	if(ans < distance(a2, b2)) __make(ans, s1, s2, a2, b2);
	if(ans < distance(a1, b2)) __make(ans, s1, s2, a1, b2);
	if(ans < distance(a2, b1)) __make(ans, s1, s2, a2, b1);
	if(ans < distance(b1, b2)) __make(ans, s1, s2, b1, b2);
}
	
inline void pushup(int p)
{
	__pushup(tree[p][0], tree[p][1], tree[DXA(p)][0], tree[DXA(p)][1], tree[DXB(p)][0], tree[DXB(p)][1]);
}
	
void pre(int l, int r, int p)
{
	if(l == r)
	{
		tree[p][0] = tree[p][1] = l;
		return ;
	}
	int mid = midf(l, r);
	pre(l, mid, DXA(p));
	pre(mid + 1, r, DXB(p));
	pushup(p);
}
	
int l, r, ans1, ans2;
void query(int nl, int nr, int p)
{
	if(l <= nl && nr <= r)
	{
		__pushup(ans1, ans2, tree[p][0], tree[p][1], ans1, ans2);
		return ;
	}
	int mid = midf(nl, nr);
	if(l <= mid) query(nl, mid, DXA(p));
	if(mid < r)  query(mid + 1, nr, DXB(p));
}
	
int main()
{
	int a, b, c, d, a1, a2, b1, b2;
	ll ans, val;
	scanf("%d", &n);
	cnt = cnt_hld = 0;
	for(register int i = 1, f, t; i < n; ++ i)
	{
		scanf("%d %d %lld", &f, &t, &val);
		addedge(f, t, val);
		addedge(t, f, val);
	}
	dis[1] = 0;
	dfs1(1, 0, 0);
	rmqinit();
	pre(1, n, 1);
	scanf("%d", &m);
	while(m --)
	{
		scanf("%d %d %d %d", &a, &b, &c, &d);
		ans = 0;
		ans1 = a, ans2 = a;
		l = a, r = b;
		query(1, n, 1);
		a1 = ans1, a2 = ans2;
		ans1 = c, ans2 = c;
		l = c, r = d;
		query(1, n, 1);
		b1 = ans1, b2 = ans2;
		ans = max(ans, distance(a1, b1));
		ans = max(ans, distance(a2, b1));
		ans = max(ans, distance(a1, b2));
		ans = max(ans, distance(a2, b2));
		printf("%lld\n", ans);
	}
	return 0;
}

XDOJ 1381 真姬的路径设计

有一棵有 $n$ 个节点的根节点为 $1$ 的树，每次只能挑一条不经过重复节点的路径去走。每次不能去走到 $x$ 和 $y$ 的子树中。请你帮她设计出一条最长的路径。注意如果没有这样的路径，输出 Maki Design Failed （用来区别路径长度为 0 和没有路径的情况）。

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
#include <bits/stdc++.h>
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) (((_) << 1))
# define DXB(_) (((_) << 1) | 1)
	
# define next __Chtholly__
# define distance __Mercury__
# define y1 __bbtl04__
# define fpos __ikooo__
	
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int MOD = 1e9 + 7;
const int maxn = 100009;
const int maxm = 100009;
int n, m, cnt, cnt_hld, cnt_pl;
int fir[maxn], dfs_time[maxn << 1], deep[maxn], fpos[maxn], pos[maxn], st2[maxn << 1][21], log_2[maxn << 1];
int dis[maxn], siz[maxn], pos2[maxn];
	
struct edg
{
	int to, next;
}edg1[maxn << 1];
	
inline void addedge(int f, int t)
{
	edg1[++ cnt].to = t;
	edg1[cnt].next = fir[f];
	fir[f] = cnt;
}
	
void dfs1(int u, int fa, int dep)
{
	siz[u] = 1;
	pos[u] = ++ cnt_pl;
	fpos[cnt_pl] = u;
	dfs_time[++ cnt_hld] = u;
	pos2[u] = cnt_hld;
	deep[u] = dep;
	for(register int i = fir[u], v; i; i = edg1[i].next)
		if((v = edg1[i].to) != fa)
		{
			dis[v] = dis[u] + 1;
			dfs1(v, u, dep + 1);
			dfs_time[++ cnt_hld] = u;
			siz[u] += siz[v];
		}
}
	
inline void rmqinit()
{
	for(register int i = 1; i <= cnt_hld; ++ i)
		st2[i][0] = dfs_time[i];
	for(register int i = 1; i <= 20; ++ i)
		for(register int j = 1; j + (1 << i) - 1 <= cnt_hld; ++ j)
		{
			if(deep[st2[j][i - 1]] < deep[st2[j + (1 << (i - 1))][i - 1]])
				st2[j][i] = st2[j][i - 1];
			else st2[j][i] = st2[j + (1 << (i - 1))][i - 1];
		}
	log_2[1] = 0;
	for(register int i = 2; i <= cnt_hld; ++ i)
	{
		if((1 << (log_2[i - 1] + 1)) < i) log_2[i] = log_2[i - 1] + 1;
		else log_2[i] = log_2[i - 1];
	}
}
	
int RMQ(int x, int y)
{
	int a = log_2[y - x + 1];
	if(deep[st2[x][a]] < deep[st2[y - (1 << a) + 1][a]])
		return st2[x][a];
	return st2[y - (1 << a) + 1][a];
}
	
ll distance(int x, int y)
{
	if(pos2[x] > pos2[y]) swap(x, y);
	int LCA = RMQ(pos2[x], pos2[y]);
	return dis[x] + dis[y] - (dis[LCA] << 1);
}
	
int tree[maxn << 2][2];
	
inline void __make(ll &ans, int &s1, int &s2, int v1, int v2)
{
	ans = distance(v1, v2), s1 = v1, s2 = v2;
}
	
inline void __pushup(int &s1, int &s2, int a1, int a2, int b1, int b2)
{
	ll ans = 0;
	if(ans < distance(a1, a2)) __make(ans, s1, s2, a1, a2);
	if(ans < distance(a1, b1)) __make(ans, s1, s2, a1, b1);
	if(ans < distance(a2, b2)) __make(ans, s1, s2, a2, b2);
	if(ans < distance(a1, b2)) __make(ans, s1, s2, a1, b2);
	if(ans < distance(a2, b1)) __make(ans, s1, s2, a2, b1);
	if(ans < distance(b1, b2)) __make(ans, s1, s2, b1, b2);
}
	
inline void pushup(int p)
{
	__pushup(tree[p][0], tree[p][1], tree[DXA(p)][0], tree[DXA(p)][1], tree[DXB(p)][0], tree[DXB(p)][1]);
}
	
void pre(int l, int r, int p)
{
	if(l == r)
	{
		tree[p][0] = tree[p][1] = fpos[l];
		return ;
	}
	int mid = midf(l, r);
	pre(l, mid, DXA(p));
	pre(mid + 1, r, DXB(p));
	pushup(p);
}
	
int l, r, ans1, ans2;
void query(int nl, int nr, int p)
{
	if(l <= nl && nr <= r)
	{
		__pushup(ans1, ans2, tree[p][0], tree[p][1], ans1, ans2);
		return ;
	}
	int mid = midf(nl, nr);
	if(l <= mid) query(nl, mid, DXA(p));
	if(mid < r)  query(mid + 1, nr, DXB(p));
}
	
int main()
{
	int a, b, c, d, a1, a2, sx, sy, ex, ey;
	ll ans, val;
	scanf("%d %d", &n, &m);
	cnt = cnt_hld = cnt_pl = 0;
	for(register int i = 1, f, t; i < n; ++ i)
	{
		scanf("%d %d", &f, &t);
		addedge(f, t);
		addedge(t, f);
	}
	dis[1] = 0;
	dfs1(1, 0, 0);
	rmqinit();
	pre(1, n, 1);
	while(m --)
	{
		scanf("%d %d", &a, &b);
		ans = -1;
		if(pos[a] > pos[b]) swap(a, b);
		sx = pos[a], ex = sx + siz[a] - 1;
		sy = pos[b], ey = sy + siz[b] - 1;
		a1 = a2 = 1;
		if(sx > 1)
		{
			ans1 = ans2 = 1;
			l = 1, r = sx - 1;
			query(1, n, 1);
			if(ans < distance(ans1, ans2)) __make(ans, a1, a2, ans1, ans2);
		}
		if(ex + 1 < sy)
		{
			ans1 = a1, ans2 = a2;
			l = ex + 1, r = sy - 1;
			query(1, n, 1);
			if(ans < distance(ans1, ans2)) __make(ans, a1, a2, ans1, ans2);
		}
		if(max(ex, ey) < n)
		{
			ans1 = a1, ans2 = a2;
			l = max(ex, ey) + 1, r = n;
			query(1, n, 1);
			if(ans < distance(ans1, ans2)) __make(ans, a1, a2, ans1, ans2);
		}
		if(ans == -1) puts("Maki Design Failed");
		else printf("%lld\n", ans);
	}
	return 0;
}
/*
5 3
1 3
3 2
3 4
2 5
2 4
5 4
1 3
*/

XDOJ 1392 天才 J 、 Satan 和初夏

求出断开一条边以后，两棵树的最长直径之和。

求出树的直径以后，需要再次遍历整棵树，枚举两个断开的区间。

计当前点在 DFS 序上及其子树上的区间为 $[x_i, y_i]$ 。

那么断开该点与其父亲所在的边所得到的结果是 $[1, x_i-1] \or [y_i + 1, n]$ 得到的直径以及 $[x_i, y_i]$ 得到的直径之和。（当然，在代码实现上，如果 $x_i=1$ 或者 $y_i=n$ 的话，直接就忽略这个区间）

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
221
222
223
224
225
226
227
228
229
230
231
232
233
#include <bits/stdc++.h>
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define mp make_pair
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) (((_) << 1))
# define DXB(_) (((_) << 1) | 1)
	
# define next __Chtholly__
# define distance __Mercury__
# define y1 __bbtl04__
# define fpos __ikooo__
	
using namespace std;
	
typedef long long ll;
const int maxn = 100009;
const int maxm = 100009;
const ll inf = 1e18;
const double pi = acos(-1.0);
const double eps = 1e-6;
int n, m, cnt, cnt_hld, cnt_pl;
int fir[maxn], dfs_time[maxn << 1], deep[maxn], fpos[maxn], pos[maxn], st2[maxn << 1][21], log_2[maxn << 1];
int siz[maxn], pos2[maxn];
ll dis[maxn];
	
struct edg
{
	int to, next;
	ll val;
}edg1[maxn << 1];
	
inline void addedge(int f, int t, ll val)
{
	edg1[++ cnt].to = t;
	edg1[cnt].next = fir[f];
	edg1[cnt].val = val;
	fir[f] = cnt;
}
	
void dfs1(int u, int fa, int dep)
{
	siz[u] = 1;
	pos[u] = ++ cnt_pl;
	fpos[cnt_pl] = u;
	dfs_time[++ cnt_hld] = u;
	pos2[u] = cnt_hld;
	deep[u] = dep;
	for(register int i = fir[u], v; i; i = edg1[i].next)
		if((v = edg1[i].to) != fa)
		{
			dis[v] = dis[u] + edg1[i].val;
			dfs1(v, u, dep + 1);
			dfs_time[++ cnt_hld] = u;
			siz[u] += siz[v];
		}
}
	
inline void rmqinit()
{
	for(register int i = 1; i <= cnt_hld; ++ i)
		st2[i][0] = dfs_time[i];
	for(register int i = 1; i <= 20; ++ i)
		for(register int j = 1; j + (1 << i) - 1 <= cnt_hld; ++ j)
		{
			if(deep[st2[j][i - 1]] < deep[st2[j + (1 << (i - 1))][i - 1]])
				st2[j][i] = st2[j][i - 1];
			else st2[j][i] = st2[j + (1 << (i - 1))][i - 1];
		}
	log_2[1] = 0;
	for(register int i = 2; i <= cnt_hld; ++ i)
	{
		if((1 << (log_2[i - 1] + 1)) < i) log_2[i] = log_2[i - 1] + 1;
		else log_2[i] = log_2[i - 1];
	}
}
	
int RMQ(int x, int y)
{
	int a = log_2[y - x + 1];
	if(deep[st2[x][a]] < deep[st2[y - (1 << a) + 1][a]])
		return st2[x][a];
	return st2[y - (1 << a) + 1][a];
}
	
ll distance(int x, int y)
{
	if(pos2[x] > pos2[y]) swap(x, y);
	int LCA = RMQ(pos2[x], pos2[y]);
	return dis[x] + dis[y] - (dis[LCA] << 1);
}
	
int tree[maxn << 2][2];
	
inline void __make(ll &ans, int &s1, int &s2, int v1, int v2)
{
	ans = distance(v1, v2), s1 = v1, s2 = v2;
}
	
inline void __pushup(int &s1, int &s2, int a1, int a2, int b1, int b2)
{
	ll ans = 0;
	if(ans < distance(a1, a2)) __make(ans, s1, s2, a1, a2);
	if(ans < distance(a1, b1)) __make(ans, s1, s2, a1, b1);
	if(ans < distance(a2, b2)) __make(ans, s1, s2, a2, b2);
	if(ans < distance(a1, b2)) __make(ans, s1, s2, a1, b2);
	if(ans < distance(a2, b1)) __make(ans, s1, s2, a2, b1);
	if(ans < distance(b1, b2)) __make(ans, s1, s2, b1, b2);
}
	
inline void pushup(int p)
{
	__pushup(tree[p][0], tree[p][1], tree[DXA(p)][0], tree[DXA(p)][1], tree[DXB(p)][0], tree[DXB(p)][1]);
}
	
void pre(int l, int r, int p)
{
	if(l == r)
	{
		tree[p][0] = tree[p][1] = fpos[l];
		return ;
	}
	int mid = midf(l, r);
	pre(l, mid, DXA(p));
	pre(mid + 1, r, DXB(p));
	pushup(p);
}
	
int l, r, ans1, ans2;
void query(int nl, int nr, int p)
{
	if(l <= nl && nr <= r)
	{
		__pushup(ans1, ans2, tree[p][0], tree[p][1], ans1, ans2);
		return ;
	}
	int mid = midf(nl, nr);
	if(l <= mid) query(nl, mid, DXA(p));
	if(mid < r)  query(mid + 1, nr, DXB(p));
}
	
ll vbegin, vend, vmid, ans, val;
void dfs2(int x, int fa)
{
	for(register int i = fir[x], v, st, ed, aa, bb, xx, yy; i; i = edg1[i].next)
	{
		if((v = edg1[i].to) != fa)
		{
			vbegin = vend = vmid = 0;
			st = pos[v], ed = pos[v] + siz[v] - 1;
			if(st == 1)
			{
				l = 1, r = ed;
				ans1 = ans2 = x;
				query(1, n, 1);
				__make(vbegin, ans1, ans2, ans1, ans2);
				l = ed + 1, r = n;
				ans1 = ans2 = v;
				query(1, n, 1);
				__make(vmid, ans1, ans2, ans1, ans2);
			}
			else if(ed == n)
			{
				l = 1, r = st - 1;
				ans1 = ans2 = x;
				query(1, n, 1);
				__make(vmid, ans1, ans2, ans1, ans2);
				l = st, r = ed;
				ans1 = ans2 = v;
				query(1, n, 1);
				__make(vend, ans1, ans2, ans1, ans2);
			}
			else 
			{
				l = 1, r = st - 1;
				ans1 = ans2 = 0;
				query(1, n, 1);
				__make(vbegin, aa, bb, ans1, ans2);
				
				l = ed + 1, r = n;
				ans1 = ans2 = 0;
				query(1, n, 1);
				if(vbegin < distance(aa, ans1)) __make(vbegin, xx, yy, aa, ans1);
				if(vbegin < distance(aa, ans2)) __make(vbegin, xx, yy, aa, ans2);
				if(vbegin < distance(bb, ans1)) __make(vbegin, xx, yy, bb, ans1);
				if(vbegin < distance(bb, ans2)) __make(vbegin, xx, yy, bb, ans2);
				
				l = st, r = ed;
				ans1 = ans2 = v;
				query(1, n, 1);
				__make(vmid, ans1, ans2, ans1, ans2);
			}
			ans = max(ans, vbegin + vmid + vend);
			dfs2(v, x);
		}
	}
}
	
int main()
{
	int a, b, c, d, a1, a2, sx, sy, ex, ey;
	scanf("%d", &n);
	cnt = cnt_hld = cnt_pl = 0;
	for(register int i = 1, f, t; i < n; ++ i)
	{
		scanf("%d %d %lld", &f, &t, &val);
		addedge(f, t, val);
		addedge(t, f, val);
	}
	dis[1] = 0;
	dfs1(1, 0, 0);
	rmqinit();
	pre(1, n, 1);
	ans = 0;
	dfs2(1, 1);
	printf("%lld\n", ans);
	return 0;
}
/*
4
1 2 34
2 3 1
3 4 123
*/

XDOJ 1389 Love Live! 高坂穗乃果篇 / HDU 5993 Tower Attack

求断掉两条边以后，形成的三棵子树的最大直径。

记两个点所对应的区间为 $[x_1, y_1], [x_2, y_2] \ (x_1 \leq x_2)$

如果断开的两个点的 LCA 是其中一个点 ($[x_1, y_1]$) 的话，三个区间是 $[1, x_1) \or (y_1, n], \ [x_1, x_2) \or (y_2, y_1], \ [x_2, y_2]$ ；

否则，三个区间是 $[1, x_1) \or (y_1,x_2) \or (y_2, n], [x_1, y_1], [x_2, y_2]$ 。

原理是连续的区间的点被取出子树以后所形成的区间为上述。

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
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
#include <bits/stdc++.h>
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define mp make_pair
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) (((_) << 1))
# define DXB(_) (((_) << 1) | 1)
	
# define next __Chtholly__
# define distance __Mercury__
# define y1 __bbtl04__
# define fpos __ikooo__
	
using namespace std;
	
typedef long long ll;
const int maxn = 100009;
const int maxm = 200009;
const ll inf = 1e18;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
int n, m, cnt, cnt_hld, cnt_pl;
int fir[maxn], dfs_time[maxn << 1], deep[maxn], fpos[maxn], pos[maxn];
int st2[maxn << 1][21], log_2[maxn << 1], father[maxn];
int siz[maxn], pos2[maxn];
int dis[maxn];
	
struct edg
{
    int to, next, val;
}edg1[maxn << 1];
	
inline void addedge(int f, int t, int val)
{
    edg1[++ cnt].to = t;
    edg1[cnt].next = fir[f];
    edg1[cnt].val = val;
    fir[f] = cnt;
}
	
void dfs1(int u)
{
    siz[u] = 1;
    pos[u] = ++ cnt_pl;
    fpos[cnt_pl] = u;
    dfs_time[++ cnt_hld] = u;
    pos2[u] = cnt_hld;
    for(register int i = fir[u], v; i; i = edg1[i].next)
        if((v = edg1[i].to) != father[u])
        {
        	father[v] = u;
        	deep[v] = deep[u] + 1;
            dis[v] = dis[u] + edg1[i].val;
            dfs1(v);
            dfs_time[++ cnt_hld] = u;
            siz[u] += siz[v];
        }
}
	
inline void rmqinit()
{
    for(register int i = 1; i <= cnt_hld; ++ i)
        st2[i][0] = dfs_time[i];
    for(register int i = 1; i <= 20; ++ i)
        for(register int j = 1; j + (1 << i) - 1 <= cnt_hld; ++ j)
        {
            if(deep[st2[j][i - 1]] < deep[st2[j + (1 << (i - 1))][i - 1]])
                st2[j][i] = st2[j][i - 1];
            else st2[j][i] = st2[j + (1 << (i - 1))][i - 1];
        }
}
	
inline int RMQ(int x, int y)
{
	if(x > y) swap(x, y);
    int a = log_2[y - x + 1];
    if(deep[st2[x][a]] < deep[st2[y - (1 << a) + 1][a]])
        return st2[x][a];
    return st2[y - (1 << a) + 1][a];
}
	
inline int distance(int x, int y)
{
    int LCA = RMQ(pos2[x], pos2[y]);
    return dis[x] + dis[y] - (dis[LCA] << 1);
}
	
int tree[maxn << 2][2];
	
inline void __make(int &ans, int &s1, int &s2, int v1, int v2)
{
    ans = distance(v1, v2), s1 = v1, s2 = v2;
}
	
inline void __pushup(int &s1, int &s2, int a1, int a2, int b1, int b2)
{
    int ans = 0;
    if(ans < distance(a1, a2)) __make(ans, s1, s2, a1, a2);
    if(ans < distance(a1, b1)) __make(ans, s1, s2, a1, b1);
    if(ans < distance(a2, b2)) __make(ans, s1, s2, a2, b2);
    if(ans < distance(a1, b2)) __make(ans, s1, s2, a1, b2);
    if(ans < distance(a2, b1)) __make(ans, s1, s2, a2, b1);
    if(ans < distance(b1, b2)) __make(ans, s1, s2, b1, b2);
}
	
inline void pushup(int p)
{
    __pushup(tree[p][0], tree[p][1], tree[DXA(p)][0], tree[DXA(p)][1], tree[DXB(p)][0], tree[DXB(p)][1]);
}
	
void pre(int l, int r, int p)
{
    if(l == r)
    {
        tree[p][0] = tree[p][1] = fpos[l];
        return ;
    }
    int mid = midf(l, r);
    pre(l, mid, DXA(p));
    pre(mid + 1, r, DXB(p));
    pushup(p);
}
	
int l, r, ans1, ans2;
void query(int nl, int nr, int p)
{
    if(l <= nl && nr <= r)
    {
        __pushup(ans1, ans2, tree[p][0], tree[p][1], ans1, ans2);
        return ;
    }
    int mid = midf(nl, nr);
    if(l <= mid) query(nl, mid, DXA(p));
    if(mid < r)  query(mid + 1, nr, DXB(p));
}
	
struct edg_2
{
    int f, t;
    edg_2(int f = -1, int t = -1) : f(f), t(t) {}
}edg2[maxn];
	
int tmp, val;
inline void makeans(int l1, int r1, int l2, int r2, int l3, int r3, int &ans)
{
    int aa, bb, aaa, bbb;
    if(l1 <= r1)
    {
	    l = l1, r = r1;
	    ans1 = ans2 = 0;
	    query(1, n, 1);
	    aa = ans1, bb = ans2;
	}
	if(l2 <= r2)
	{
	    l = l2, r = r2;
	    ans1 = ans2 = 0;
	    query(1, n, 1);
	    aaa = ans1, bbb = ans2;
	}
	if(l3 <= r3)
	{
	    l = l3, r = r3;
	    ans1 = ans2 = 0;
	    query(1, n, 1);
	}
    __pushup(aaa, bbb, aaa, bbb, aa, bb);
    __pushup(ans1, ans2, aaa, bbb, ans1, ans2);
    if(ans < distance(ans1, ans2)) ans = distance(ans1, ans2);
}
	
inline void makeans(int l1, int r1, int l2, int r2, int &ans)
{
    int aa, bb;
    l = l1, r = r1;
    ans1 = ans2 = 0;
    query(1, n, 1);
    aa = ans1, bb = ans2;
    l = l2, r = r2;
    ans1 = ans2 = 0;
    query(1, n, 1);
    __pushup(ans1, ans2, ans1, ans2, aa, bb);
    if(ans < distance(ans1, ans2)) ans = distance(ans1, ans2);
}
	
inline void makeans(int l1, int r1, int &ans)
{
    l = l1, r = r1;
    ans1 = ans2 = 0;
    query(1, n, 1);
    if(ans < distance(ans1, ans2)) ans = distance(ans1, ans2);
}
	
int main()
{
    int ans;
    log_2[1] = 0;
    for(register int i = 2; i < (maxn << 1); ++ i)
    {
        if((1 << (log_2[i - 1] + 1)) < i) log_2[i] = log_2[i - 1] + 1;
        else log_2[i] = log_2[i - 1];
    }
    scan_d(n); scan_d(m);
    RESET(fir);
    cnt = cnt_hld = cnt_pl = 0;
    for(register int i = 1, f, t; i < n; ++ i)
    {
        scan_d(f), scan_d(t), scan_d(val);
        edg2[i] = edg_2(f, t);
        addedge(f, t, val);
        addedge(t, f, val);
    }
    dis[1] = 0;
    deep[1] = father[1] = 0;
    dfs1(1);
    rmqinit();
    pre(1, n, 1);
    ans = 0;
    for(register int i = 1; i < n; ++ i)
    {
        if(deep[edg2[i].f] > deep[edg2[i].t])
            swap(edg2[i].f, edg2[i].t);
    }
    for(register int Case = 1, f, t, w, sx, ex, sy, ey; Case <= m; ++ Case)
    {
        scan_d(f), scan_d(t);
        ans = 0;
        f = edg2[f].t, t = edg2[t].t;
        w = RMQ(pos2[f], pos2[t]);
        if(f == w || t == w)
        {
            if(f != w) swap(t, f);
            sx = pos[f], ex = pos[f] + siz[f] - 1;
            sy = pos[t], ey = pos[t] + siz[t] - 1;
            
            makeans(1, sx - 1, ex + 1, n, ans);
            makeans(sx, sy - 1, ey + 1, ex, ans);
            makeans(sy, ey, ans);
        }
        else 
        {
            if(pos[f] > pos[t]) swap(f, t);
            sx = pos[f], ex = pos[f] + siz[f] - 1;
            sy = pos[t], ey = pos[t] + siz[t] - 1;
            
            makeans(1, sx - 1, ex + 1, sy - 1, ey + 1, n, ans);
            makeans(sx, ex, ans);
            makeans(sy, ey, ans);
        }
        printf("%d\n", ans);
    }
    return 0;
}
/*
1
8 3
2 1 7
3 1 7
4 2 5
5 2 6
4 6 3
7 2 8
1 8 2
4 6
2 3
5 6
*/

如果被卡常的话，试试下面的代码

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
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int T, n, m;
int len, head[N], ST[20][N];
struct edge{int u, v, w;}ee[N];
int cnt, fa[N], log_2[N], st[N], en[N], dfn[N], dis[N], dep[N], pos[N];
struct edges{int to, next, cost;}e[N];
inline void add(int u, int v, int w) {
    e[++ len] = (edges){v, head[u], w}, head[u] = len;
    e[++ len] = (edges){u, head[v], w}, head[v] = len;
}
inline void dfs1(int u) {
    st[u] = ++ cnt, dfn[cnt] = u;
    for (int v, i = head[u]; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa[u]) continue;
        fa[v] = u, dep[v] = dep[u] + 1;
        dis[v] = dis[u] + e[i].cost, dfs1(v);
    }
    en[u] = cnt;
}
inline void dfs2(int u) {
    dfn[++ cnt] = u, pos[u] = cnt;
    for (int v, i = head[u]; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa[u]) continue;
        dfs2(v), dfn[++ cnt] = u;
    }
}
int mmin(int x, int y) {
    if (dep[x] < dep[y]) return x;
    return y;
}
inline int lca(int u, int v) {
    static int w;
    if (pos[u] > pos[v]) swap(u, v);
    w = log_2[pos[v] - pos[u] + 1];
    return mmin(ST[w][pos[u]], ST[w][pos[v] - (1 << w) + 1]);
}
inline int dist(int u, int v) {
    int Lca = lca(u, v);
    return dis[u] + dis[v] - dis[Lca] * 2;
}
inline void build() {
    for (int i = 1; i <= cnt; i ++)
        ST[0][i] = dfn[i];
    for (int i = 1; i < 20; i ++)
        for (int j = 1; j <= cnt; j ++)
            if (j + (1 << (i - 1)) > cnt) ST[i][j] = ST[i - 1][j];
            else ST[i][j] = mmin(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]); 
}
int M;
struct node {
    int l, r, dis;
}tr[N << 1];
inline void update(int o, int o1, int o2) {
    static int d;
    static node tmp;
    if (tr[o1].dis == -1) {tr[o] = tr[o2]; return;}
    if (tr[o2].dis == -1) {tr[o] = tr[o1]; return;}
    if (tr[o1].dis > tr[o2].dis) tmp = tr[o1];
    else tmp = tr[o2]; 
    d = dist(tr[o1].l, tr[o2].l);
    if (d > tmp.dis) tmp.l = tr[o1].l, tmp.r = tr[o2].l, tmp.dis = d;
    d = dist(tr[o1].l, tr[o2].r);
    if (d > tmp.dis) tmp.l = tr[o1].l, tmp.r = tr[o2].r, tmp.dis = d;
    d = dist(tr[o1].r, tr[o2].l);
    if (d > tmp.dis) tmp.l = tr[o1].r, tmp.r = tr[o2].l, tmp.dis = d;
    d = dist(tr[o1].r, tr[o2].r);
    if (d > tmp.dis) tmp.l = tr[o1].r, tmp.r = tr[o2].r, tmp.dis = d;
    tr[o] = tmp;
}
inline void ask(int s, int t) {
    if (s > t) return;
    for (s += M - 1, t += M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
        if (~s&1) update(0, 0, s ^ 1);
        if ( t&1) update(0, 0, t ^ 1);
    }
}
inline int get_char() {
    static const int SIZE = 1 << 23;
    static char *T, *S = T, buf[SIZE];
    if (S == T) {
        T = fread(buf, 1, SIZE, stdin) + (S = buf);
        if (S == T) return -1;
    }
    return *S ++;
}
 
inline void in(int &x) {
    static int ch;
    while (ch = get_char(), ch > 57 || ch < 48);x = ch - 48;
    while (ch = get_char(), ch > 47 && ch < 58) x = x * 10 + ch - 48;
}
int main() {
    int u, v, w, ans;
    log_2[1] = 0;
    for (int i = 2; i <= 200000; i ++) 
        if (i == 1 << (log_2[i - 1] + 1))
            log_2[i] = log_2[i - 1] + 1;
        else log_2[i] = log_2[i - 1];
    for (in(T); T --; ) {
        in(n), in(m), cnt = len = 0;
        for (int i = 1; i <= n; i ++)
            head[i] = 0;
        for (int i = 1; i < n; i ++) {
            in(ee[i].u), in(ee[i].v), in(ee[i].w);
            add(ee[i].u, ee[i].v, ee[i].w);
        }
        dfs1(1);
        for (M = 1; M < n + 2; M <<= 1);
        for (int i = 1; i <= n; i ++)
            tr[i + M].l = tr[i + M].r = dfn[i], tr[i + M].dis = 0;
        for (int i = n + M + 1; i <= (M << 1) + 1; i ++)
            tr[i].dis = -1;
        cnt = 0, dfs2(1), build();
        for (int i = M; i; i --) 
            update(i, i << 1, i << 1 | 1);
        for (int i = 1; i < n; i ++) 
            if (dep[ee[i].u] > dep[ee[i].v])
                swap(ee[i].u, ee[i].v);
        for (int u, v, i = 1; i <= m; i ++) {
            in(u), in(v), ans = 0;
            u = ee[u].v, v = ee[v].v, w = lca(u, v);
            if (w == u || w == v) {
                if (w != u) swap(u, v);
                tr[0].dis = -1, ask(1, st[u] - 1), ask(en[u] + 1, n), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[u], st[v] - 1), ask(en[v] + 1, en[u]), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[v], en[v]), ans = max(ans, tr[0].dis);
            }
            else {
                if (st[u] > st[v]) swap(u, v);
                tr[0].dis = -1, ask(1, st[u] - 1), ask(en[u] + 1, st[v] - 1), ask(en[v] + 1, n), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[u], en[u]), ans = max(ans, tr[0].dis);
                tr[0].dis = -1, ask(st[v], en[v]), ans = max(ans, tr[0].dis);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

本文标题:线段树维护树的直径

文章作者:Babydragon

发布时间:2018-09-02, 01:20:00

最后更新:2018-11-16, 12:48:47

原始链接:http://baolintian.github.io/2018/09/02/线段树维护树的直径/

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

文章目录
  1. 1. 线段树维护树的直径
    1. 1.1. 概述
    2. 1.2. 本文可以解决的问题
    3. 1.3. 算法流程
    4. 1.4. 应用
      1. 1.4.1. XDOJ 1380 小萌和小明
      2. 1.4.2. XDOJ 1381 真姬的路径设计
      3. 1.4.3. XDOJ 1392 天才 J 、 Satan 和初夏
      4. 1.4.4. XDOJ 1389 Love Live! 高坂穗乃果篇 / HDU 5993 Tower Attack
{{ live2d() }}