线段树求直径可以求任意子树（包括连子树都不算的分散节点集合）的直径，适用范围广。

线段树的每个节点所对应的区间$[L, R]$，指代了$Dfn$在$[L, R]$内节点，其中线段树上每个节点存储了$diam$（当前区间直径）及$lp, rp$（当前直径对应的左右端点），每次$Merge$操作分为全左区间、全右区间和横跨两个区间作讨论，对于第三种情况，选择两侧原直径端点求$Dist$取最值即可，正确性显然，查询直接通过$Dfn$查询即可。

当然可能有一些区间内的点不连通，先当作它们连通即可。

对于删除某些子树，相当于把整棵树分为$n$部分，查询每个部分，全部$Merge$起来即可。

例题

Snow的追寻

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
1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 #define lson root << 1
  8 #define rson root << 1 | 1
  9 
 10 using namespace std;
 11 
 12 const int MAXN = 1e05 + 10;
 13 const int MAXM = 1e05 + 10;
 14 
 15 struct LinkedForwardStar {
 16     int to;
 17 
 18     int next;
 19 } ;
 20 
 21 LinkedForwardStar Link[MAXM << 1];
 22 int Head[MAXN]= {0};
 23 int size = 0;
 24 
 25 void Insert (int u, int v) {
 26     Link[++ size].to = v;
 27     Link[size].next = Head[u];
 28 
 29     Head[u] = size;
 30 }
 31 
 32 const int Root = 1;
 33 
 34 int Deep[MAXN];
 35 int Size[MAXN];
 36 int Val[MAXN << 1];
 37 int Dfn[MAXN], DDfn[MAXN];
 38 int Rank[MAXN];
 39 int dfsord = 0, dod2 = 0;
 40 
 41 void DFS (int root, int father) {
 42     Size[root] = 1;
 43     Dfn[root] = ++ dfsord;
 44     Rank[dfsord] = root;
 45     DDfn[root] = ++ dod2;
 46     Val[dod2] = Deep[root];
 47     for (int i = Head[root]; i; i = Link[i].next) {
 48         int v = Link[i].to;
 49         if (v == father)
 50             continue;
 51 
 52         Deep[v] = Deep[root] + 1;
 53         DFS (v, root);
 54         Size[root] += Size[v];
 55         Val[++ dod2] = Deep[root];
 56     }
 57 }
 58 
 59 int ST[MAXN << 1][30];
 60 
 61 void RMQ () {
 62     for (int i = 1; i <= dod2; i ++)
 63         ST[i][0] = Val[i];
 64     for (int j = 1; j <= 20; j ++)
 65         for (int i = 1; i <= dod2; i ++)
 66             if (i + (1 << (j - 1)) <= dod2)
 67                 ST[i][j] = min (ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
 68 }
 69 
 70 int Query (int L, int R) {
 71     int k = log2 (R - L + 1);
 72     return min (ST[L][k], ST[R - (1 << k) + 1][k]);
 73 }
 74 
 75 int Dist (int x, int y) {
 76     if (DDfn[x] > DDfn[y])
 77         swap (x, y);
 78 
 79     int deeplca = Query (DDfn[x], DDfn[y]);
 80     return Deep[x] + Deep[y] - 2 * deeplca;
 81 }
 82 
 83 struct Node {
 84     int diam;
 85     int lp, rp;
 86 
 87     Node () {
 88         diam = 0;
 89         lp = rp = 0;
 90     }
 91 
 92     Node (int fdiam, int flp, int frp) :
 93         diam (fdiam), lp (flp), rp (frp) {}
 94 } ;
 95 
 96 Node Tree[MAXN << 2];
 97 
 98 
 99 Node Merge (Node s1, Node s2) {
100     if (s1.diam == - 1)
101         return s2;
102     Node news = s1.diam >= s2.diam ? s1 : s2; // 以下讨论
103     if (Dist (s1.lp, s2.lp) > news.diam)
104         news = Node (Dist (s1.lp, s2.lp), s1.lp, s2.lp);
105     if (Dist (s1.lp, s2.rp) > news.diam)
106         news = Node (Dist (s1.lp, s2.rp), s1.lp, s2.rp);
107     if (Dist (s1.rp, s2.lp) > news.diam)
108         news = Node (Dist (s1.rp, s2.lp), s1.rp, s2.lp);
109     if (Dist (s1.rp, s2.rp) > news.diam)
110         news = Node (Dist (s1.rp, s2.rp), s1.rp, s2.rp);
111 
112     return news;
113 }
114 
115 void Build (int root, int left, int right) {
116     Tree[root] = Node ();
117 
118     if (left == right) {
119         Tree[root].diam = 0;
120         Tree[root].lp = Tree[root].rp = Rank[left];
121         return ;
122     }
123 
124     int mid = (left + right) >> 1;
125     Build (lson, left, mid);
126     Build (rson, mid + 1, right);
127 
128     Tree[root] = Merge (Tree[lson], Tree[rson]);
129 }
130 
131 Node Query (int root, int left, int right, int L, int R) {
132     if (L == left && R == right)
133         return Tree[root];
134 
135     int mid = (left + right) >> 1;
136     if (R <= mid)
137         return Query (lson, left, mid, L, R);
138     else if (L > mid)
139         return Query (rson, mid + 1, right, L, R);
140     else
141         return Merge (Query (lson, left, mid, L, mid), Query (rson, mid + 1, right, mid + 1, R));
142 }
143 
144 int N, Q;
145 
146 int getnum () {
147     int num = 0;
148     char ch = getchar ();
149 
150     while (! isdigit (ch))
151         ch = getchar ();
152     while (isdigit (ch))
153         num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
154 
155     return num;
156 }
157 
158 int main () {
159     // freopen ("Input.txt", "r", stdin);
160 
161     N = getnum (), Q = getnum ();
162 
163     for (int i = 1; i < N; i ++) {
164         int u, v;
165         u = getnum (), v = getnum ();
166         Insert (u, v), Insert (v, u);
167     }
168 
169     DFS (Root, 0);
170     RMQ ();
171 
172     Build (Root, 1, dfsord);
173     for (int Case = 1; Case <= Q; Case ++) {
174         int x, y;
175         x = getnum (), y = getnum ();
176 
177         Node res = Node (- 1, - 1, - 1);
178         if (Dfn[x] > Dfn[y])
179             swap (x, y);
180         int sx = Dfn[x], ex = sx + Size[x] - 1;
181         int sy = Dfn[y], ey = sy + Size[y] - 1;
182         if (sx > 1) // 第一部分
183             res = Merge (res, Query (Root, 1, dfsord, 1, sx - 1));
184         if (ex + 1 < sy) // 第二部分
185             res = Merge (res, Query (Root, 1, dfsord, ex + 1, sy - 1));
186         int fen = max (ex, ey);
187         if (fen < dfsord) // 第三部分
188             res = Merge (res, Query (Root, 1, dfsord, fen + 1, dfsord));
189         printf ("%d\n", res.diam == - 1 ? 0 : res.diam);
190     }
191 
192     return 0;
193 }
194 
195 /*
196 5 2
197 1 3
198 3 2
199 3 4
200 2 5
201 2 4
202 5 4
203 */