进阶换根dp

发表于 更新于 分类于 ， 阅读次数： 本文字数： 4.3k 阅读时长 ≈ 16 分钟

战略威慑(智旭生加强版)伪题解

\(\qquad\!\!\)一句话题意：在 \(O(N)\) 的时间复杂度内求出一棵树删去一条边以后分裂成的两颗新树的直径的乘积的最大值。

\(\qquad\!\!\)相信暴力大家都会，下面就直接说一种比较麻烦的正解吧：

应用算法：换根\(dp\)

我就认为大家对于思想都理解了，我主要讲一下比较复杂的分类讨论和代码实现：

\(\qquad\!\!\)首先，我们考虑一下每个节点需要存储的数据：

\(\qquad\!\!\)由于在 \(dp\) 找直径，所以需要存一下经过每个节点向下的最长链 \(f1\) 和次长链 \(f2\)；由于新树的直径不一定过切割点，所以需要存一下每个节点的最长子树路径 \(dpf1\) ，注意这个路径不能包含该点；由于进行 换根\(dp\)，需要将旧的根的信息传递给新的根，所以需要再存一个再次长链 \(f3\) 和次长子树路径 \(dpf2\) ；由于进行 换根\(dp\)，需要确定新的根对于旧的根的信息继承，所以需要再存一下最长链的最优子节点编号 \(g1\) 和次长链的次优子节点编号 \(g2\) 以及最长子树路径的最优子节点编号 \(dpg1\)。

1
2
3
4
5
6
struct node
{
	int dpf1,dpg1,dpf2,f1,f2,f3,g1,g2;
//	int dpg2,g3;这两个的意思大家都能懂的，它们没有存储的必要，不过由于我有点强迫症，就写上+注释掉了。
};
node a[N];
\(\qquad\!\!\)其次，我们考虑初始化每个点的以上变量：

\(\qquad\!\!\)很简单的树形 \(dp\)，我们利用一次 \(dfs\) 进行处理，具体内容可自行理解。

\(\qquad\!\!\)这不会还有人不会吧？不会吧。不会吧。

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
in void dfs1(re int u,re int fa)
{
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
		{
			continue;
		}
		dfs1(v,u);
		if(max(a[v].dpf1,a[v].f1+a[v].f2)>a[u].dpf1)
		{
			a[u].dpf2=a[u].dpf1;
//			a[u].dpg2=a[u].dpg1;
			a[u].dpf1=max(a[v].dpf1,a[v].f1+a[v].f2);
			a[u].dpg1=v;
		}
		else if(max(a[v].dpf1,a[v].f1+a[v].f2)<=a[u].dpf1&&max(a[v].dpf1,a[v].f1+a[v].f2)>a[u].dpf2)
		{
			a[u].dpf2=max(a[v].dpf1,a[v].f1+a[v].f2);
//			a[u].dpg2=v;
		}
		if(a[v].f1+1>a[u].f1)
		{
			a[u].f3=a[u].f2;
//			a[u].g3=a[u].g2;
			a[u].f2=a[u].f1;
			a[u].g2=a[u].g1;
			a[u].f1=a[v].f1+1;
			a[u].g1=v;
		}
		else if(a[v].f1+1<=a[u].f1&&a[v].f1+1>a[u].f2)
		{
			a[u].f3=a[u].f2;
//			a[u].g3=a[u].g2;
			a[u].f2=a[v].f1+1;
			a[u].g2=v;
		}
		else if(a[v].f1+1<=a[u].f2&&a[v].f1+1>a[u].f3)
		{
			a[u].f3=a[v].f1+1;
//			a[u].g3=v;
		}
	}
	return ;
}
\(\qquad\!\!\)再次，我们考虑进行 换根\(dp\)：

\(\qquad\!\!\)我们利用一次 \(dfs\) 进行处理。先考虑统计答案，我们只需要根据 \(dfs\) 的顺序对于每条边不记的情况统计一次答案即可；再考虑换根的过程，我们只需要根据 \(dfs\) 的顺序将每条边的两侧的节点中的父节点（此时的根节点）的信息传递给子节点（新的根节点）即可；最后考虑一下正确性，由于换根的过程只改变新的根一个节点的信息，且回溯后此信息无用，易证该过程是正确的。

\(\qquad\!\!\)由于新的根节点与父节点存储的用于统计答案的数据存在联系，所以就需要进行分类讨论，先看一下程序的框架：

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
in void dfs2(re int u,re int fa)
{
//	for(re int i=1;i<=n;i++)
//	{
//		cout<<"u="<<u<<" i="<<i<<" "<<a[i].dpf1<<" "<<a[i].dpg1<<" "<<a[i].dpf2<<" "<<a[i].dpg2<<" "<<a[i].f1<<" "<<a[i].g1<<" "<<a[i].f2<<" "<<a[i].g2<<" "<<a[i].f3<<" "<<a[i].g3<<"\n";
//	}
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
		{
			continue;
		}
		if(v==a[u].g1)
		{
			if(v==a[u].dpg1)
			{
				情况一：统计答案+对于子树路径换根。
			}
			else
			{
				情况二：统计答案+对于子树路径换根。
			}
			情况一+情况二：统一的对于链换根。
		}
		else if(v==a[u].g2)
		{
			if(v==a[u].dpg1)
			{
				情况三：统计答案+对于子树路径换根。
			}
			else
			{
				情况四：统计答案+对于子树路径换根。
			}
			情况三+情况四：统一的对于链换根。
		}
		else
		{
			if(v==a[u].dpg1)
			{
				情况五：统计答案+对于子树路径换根。
			}
			else
			{
				情况六：统计答案+对于子树路径换根。
			}
			情况五+情况六：统一的对于链换根。
		}
		dfs2(v,u);
	}
	return ;
}

\(\qquad\!\!\)下面进行分类讨论：

  • 一、新的根 \(v\) 为父节点 \(u\) 的最长链的最优子节点 \(g1\)：

    • 情况一：新的根 \(v\) 为父节点 \(u\) 的最长子树路径的最优子节点 \(dpg1\)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //统计答案：
    ans=max(ans,max(max((a[u].f2+a[u].f3)*a[v].dpf1,a[u].dpf2*a[v].dpf1),max((a[u].f2+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf2*(a[v].f1+a[v].f2))));
    //对于子树路径换根：
    if(max(a[u].dpf2,a[u].f2+a[u].f3)>a[v].dpf1)
    {
    	a[v].dpf2=a[v].dpf1;
    //	a[v].dpg2=a[v].dpg1;
    	a[v].dpf1=max(a[u].dpf2,a[u].f2+a[u].f3);
    	a[v].dpg1=u;
    }
    else if(max(a[u].dpf2,a[u].f2+a[u].f3)<=a[v].dpf1&&max(a[u].dpf2,a[u].f2+a[u].f3)>a[v].dpf2)
    {
    	a[v].dpf2=max(a[u].dpf2,a[u].f2+a[u].f3);
    //	a[v].dpg2=u;
    }

    • 情况二：新的根 \(v\) 不为父节点 \(u\) 的最长子树路径的最优子节点 \(dpg1\)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //统计答案：
    ans=max(ans,max(max((a[u].f2+a[u].f3)*a[v].dpf1,a[u].dpf1*a[v].dpf1),max((a[u].f2+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf1*(a[v].f1+a[v].f2))));
    //对于子树路径换根：
    if(max(a[u].dpf1,a[u].f2+a[u].f3)>a[v].dpf1)
    {
    	a[v].dpf2=a[v].dpf1;
    //	a[v].dpg2=a[v].dpg1;
    	a[v].dpf1=max(a[u].dpf1,a[u].f2+a[u].f3);
    	a[v].dpg1=u;
    }
    else if(max(a[u].dpf1,a[u].f2+a[u].f3)<=a[v].dpf1&&max(a[u].dpf1,a[u].f2+a[u].f3)>a[v].dpf2)
    {
    	a[v].dpf2=max(a[u].dpf1,a[u].f2+a[u].f3);
    //	a[v].dpg2=u;
    }

    • 情况一+情况二：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //统一的对于链换根:
    if(a[u].f2+1>a[v].f1)
    {
    	a[v].f3=a[v].f2;
    //	a[v].g3=a[v].g2;
    	a[v].f2=a[v].f1;
    	a[v].g2=a[v].g1;
    	a[v].f1=a[u].f2+1;
    	a[v].g1=u;
    }
    else if(a[u].f2+1<=a[v].f1&&a[u].f2+1>a[v].f2)
    {
    	a[v].f3=a[v].f2;
    //	a[v].g3=a[v].g2;
    	a[v].f2=a[u].f2+1;
    	a[v].g2=u;
    }
    else if(a[u].f2+1<=a[v].f2&&a[u].f2+1>a[v].f3)
    {
    	a[v].f3=a[u].f2+1;
    //	a[v].g3=u;
    }

  • 二、新的根 \(v\) 为父节点 \(u\) 的次长链的次优子节点 \(g2\)：

    • 情况三：新的根 \(v\) 为父节点 \(u\) 的最长子树路径的最优子节点 \(dpg1\)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //统计答案：
    ans=max(ans,max(max((a[u].f1+a[u].f3)*a[v].dpf1,a[u].dpf2*a[v].dpf1),max((a[u].f1+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf2*(a[v].f1+a[v].f2))));
    //对于子树路径换根：
    if(max(a[u].dpf2,a[u].f1+a[u].f3)>a[v].dpf1)
    {
    	a[v].dpf2=a[v].dpf1;
    //	a[v].dpg2=a[v].dpg1;
    	a[v].dpf1=max(a[u].dpf2,a[u].f1+a[u].f3);
    	a[v].dpg1=u;
    }
    else if(max(a[u].dpf2,a[u].f1+a[u].f3)<=a[v].dpf1&&max(a[u].dpf2,a[u].f1+a[u].f3)>a[v].dpf2)
    {
    	a[v].dpf2=max(a[u].dpf2,a[u].f1+a[u].f3);
    //	a[v].dpg2=u;
    }

    • 情况四：新的根 \(v\) 不为父节点 \(u\) 的最长子树路径的最优子节点 \(dpg1\)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //统计答案：
    ans=max(ans,max(max((a[u].f1+a[u].f3)*a[v].dpf1,a[u].dpf1*a[v].dpf1),max((a[u].f1+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf1*(a[v].f1+a[v].f2))));
    //对于子树路径换根：
    if(max(a[u].dpf1,a[u].f1+a[u].f3)>a[v].dpf1)
    {
    	a[v].dpf2=a[v].dpf1;
    //	a[v].dpg2=a[v].dpg1;
    	a[v].dpf1=max(a[u].dpf1,a[u].f1+a[u].f3);
    	a[v].dpg1=u;
    }
    else if(max(a[u].dpf1,a[u].f1+a[u].f3)<=a[v].dpf1&&max(a[u].dpf1,a[u].f1+a[u].f3)>a[v].dpf2)
    {
    	a[v].dpf2=max(a[u].dpf1,a[u].f1+a[u].f3);
    //	a[v].dpg2=u;
    }

    • 情况三+情况四：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //统一的对于链换根:
    if(a[u].f1+1>a[v].f1)
    {
    	a[v].f3=a[v].f2;
    //	a[v].g3=a[v].g2;
    	a[v].f2=a[v].f1;
    	a[v].g2=a[v].g1;
    	a[v].f1=a[u].f1+1;
    	a[v].g1=u;
    }
    else if(a[u].f1+1<=a[v].f1&&a[u].f1+1>a[v].f2)
    {
    	a[v].f3=a[v].f2;
    //	a[v].g3=a[v].g2;
    	a[v].f2=a[u].f1+1;
    	a[v].g2=u;
    }
    else if(a[u].f1+1<=a[v].f2&&a[u].f1+1>a[v].f3)
    {
    	a[v].f3=a[u].f1+1;
    //	a[v].g3=u;
    }

  • 三、新的根 \(v\) 既不为父节点 \(u\) 的最长链的最优子节点 \(g1\)，又不为父节点 \(u\) 的次长链的次优子节点 \(g2\)：

    • 情况五：新的根 \(v\) 为父节点 \(u\) 的最长子树路径的最优子节点 \(dpg1\)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //统计答案：
    ans=max(ans,max(max((a[u].f1+a[u].f2)*a[v].dpf1,a[u].dpf2*a[v].dpf1),max((a[u].f1+a[u].f2)*(a[v].f1+a[v].f2),a[u].dpf2*(a[v].f1+a[v].f2))));
    //对于子树路径换根：
    if(max(a[u].dpf2,a[u].f1+a[u].f2)>a[v].dpf1)
    {
    	a[v].dpf2=a[v].dpf1;
    //	a[v].dpg2=a[v].dpg1;
    	a[v].dpf1=max(a[u].dpf2,a[u].f1+a[u].f2);
    	a[v].dpg1=u;
    }
    else if(max(a[u].dpf2,a[u].f1+a[u].f2)<=a[v].dpf1&&max(a[u].dpf2,a[u].f1+a[u].f2)>a[v].dpf2)
    {
    	a[v].dpf2=max(a[u].dpf2,a[u].f1+a[u].f2);
    //	a[v].dpg2=u;
    }

    • 情况六：新的根 \(v\) 不为父节点 \(u\) 的最长子树路径的最优子节点 \(dpg1\)：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //统计答案：
    ans=max(ans,max(max((a[u].f1+a[u].f2)*a[v].dpf1,a[u].dpf1*a[v].dpf1),max((a[u].f1+a[u].f2)*(a[v].f1+a[v].f2),a[u].dpf1*(a[v].f1+a[v].f2))));
    //对于子树路径换根：
    if(max(a[u].dpf1,a[u].f1+a[u].f2)>a[v].dpf1)
    {
    	a[v].dpf2=a[v].dpf1;
    //	a[v].dpg2=a[v].dpg1;
    	a[v].dpf1=max(a[u].dpf1,a[u].f1+a[u].f2);
    	a[v].dpg1=u;
    }
    else if(max(a[u].dpf1,a[u].f1+a[u].f2)<=a[v].dpf1&&max(a[u].dpf1,a[u].f1+a[u].f2)>a[v].dpf2)
    {
    	a[v].dpf2=max(a[u].dpf1,a[u].f1+a[u].f2);
    //	a[v].dpg2=u;
    }

    • 情况五+情况六：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //统一的对于链换根:
    if(a[u].f1+1>a[v].f1)
    {
    	a[v].f3=a[v].f2;
    //	a[v].g3=a[v].g2;
    	a[v].f2=a[v].f1;
    	a[v].g2=a[v].g1;
    	a[v].f1=a[u].f1+1;
    	a[v].g1=u;
    }
    else if(a[u].f1+1<=a[v].f1&&a[u].f1+1>a[v].f2)
    {
    	a[v].f3=a[v].f2;
    //	a[v].g3=a[v].g2;
    	a[v].f2=a[u].f1+1;
    	a[v].g2=u;
    }
    else if(a[u].f1+1<=a[v].f2&&a[u].f1+1>a[v].f3)
    {
    	a[v].f3=a[u].f1+1;
    //	a[v].g3=u;
    }

\(\qquad\!\!\)最后，上代码（懒得写注释了，自己去上面找吧……）：
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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
#include<bits/stdc++.h>
#define re register
#define in inline
#define int long long
const int N=400010;
using namespace std;
int n,head[N],ans,cnt;
struct edge
{
	int to,nxt;
};
edge e[N<<1];
struct node
{
	int dpf1,dpg1,dpf2,f1,f2,f3,g1,g2;
//	int dpg2,g3;
};
node a[N];
in int qread()
{
	int x=0,y=1;
	int ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')
		{
			y=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in void mr(re int u,re int v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	return ;
}
in void dfs1(re int u,re int fa)
{
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
		{
			continue;
		}
		dfs1(v,u);
		if(max(a[v].dpf1,a[v].f1+a[v].f2)>a[u].dpf1)
		{
			a[u].dpf2=a[u].dpf1;
//			a[u].dpg2=a[u].dpg1;
			a[u].dpf1=max(a[v].dpf1,a[v].f1+a[v].f2);
			a[u].dpg1=v;
		}
		else if(max(a[v].dpf1,a[v].f1+a[v].f2)<=a[u].dpf1&&max(a[v].dpf1,a[v].f1+a[v].f2)>a[u].dpf2)
		{
			a[u].dpf2=max(a[v].dpf1,a[v].f1+a[v].f2);
//			a[u].dpg2=v;
		}
		if(a[v].f1+1>a[u].f1)
		{
			a[u].f3=a[u].f2;
//			a[u].g3=a[u].g2;
			a[u].f2=a[u].f1;
			a[u].g2=a[u].g1;
			a[u].f1=a[v].f1+1;
			a[u].g1=v;
		}
		else if(a[v].f1+1<=a[u].f1&&a[v].f1+1>a[u].f2)
		{
			a[u].f3=a[u].f2;
//			a[u].g3=a[u].g2;
			a[u].f2=a[v].f1+1;
			a[u].g2=v;
		}
		else if(a[v].f1+1<=a[u].f2&&a[v].f1+1>a[u].f3)
		{
			a[u].f3=a[v].f1+1;
//			a[u].g3=v;
		}
	}
	return ;
}
in void dfs2(re int u,re int fa)
{
//	for(re int i=1;i<=n;i++)
//	{
//		cout<<"u="<<u<<" i="<<i<<" "<<a[i].dpf1<<" "<<a[i].dpg1<<" "<<a[i].dpf2<<" "<<a[i].dpg2<<" "<<a[i].f1<<" "<<a[i].g1<<" "<<a[i].f2<<" "<<a[i].g2<<" "<<a[i].f3<<" "<<a[i].g3<<"\n";
//	}
	for(re int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
		{
			continue;
		}
		if(v==a[u].g1)
		{
			if(v==a[u].dpg1)
			{
				ans=max(ans,max(max((a[u].f2+a[u].f3)*a[v].dpf1,a[u].dpf2*a[v].dpf1),max((a[u].f2+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf2*(a[v].f1+a[v].f2))));
				if(max(a[u].dpf2,a[u].f2+a[u].f3)>a[v].dpf1)
				{
					a[v].dpf2=a[v].dpf1;
//					a[v].dpg2=a[v].dpg1;
					a[v].dpf1=max(a[u].dpf2,a[u].f2+a[u].f3);
					a[v].dpg1=u;
				}
				else if(max(a[u].dpf2,a[u].f2+a[u].f3)<=a[v].dpf1&&max(a[u].dpf2,a[u].f2+a[u].f3)>a[v].dpf2)
				{
					a[v].dpf2=max(a[u].dpf2,a[u].f2+a[u].f3);
//					a[v].dpg2=u;
				}
			}
			else
			{
				ans=max(ans,max(max((a[u].f2+a[u].f3)*a[v].dpf1,a[u].dpf1*a[v].dpf1),max((a[u].f2+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf1*(a[v].f1+a[v].f2))));
				if(max(a[u].dpf1,a[u].f2+a[u].f3)>a[v].dpf1)
				{
					a[v].dpf2=a[v].dpf1;
//					a[v].dpg2=a[v].dpg1;
					a[v].dpf1=max(a[u].dpf1,a[u].f2+a[u].f3);
					a[v].dpg1=u;
				}
				else if(max(a[u].dpf1,a[u].f2+a[u].f3)<=a[v].dpf1&&max(a[u].dpf1,a[u].f2+a[u].f3)>a[v].dpf2)
				{
					a[v].dpf2=max(a[u].dpf1,a[u].f2+a[u].f3);
//					a[v].dpg2=u;
				}
			}
			if(a[u].f2+1>a[v].f1)
			{
				a[v].f3=a[v].f2;
//				a[v].g3=a[v].g2;
				a[v].f2=a[v].f1;
				a[v].g2=a[v].g1;
				a[v].f1=a[u].f2+1;
				a[v].g1=u;
			}
			else if(a[u].f2+1<=a[v].f1&&a[u].f2+1>a[v].f2)
			{
				a[v].f3=a[v].f2;
//				a[v].g3=a[v].g2;
				a[v].f2=a[u].f2+1;
				a[v].g2=u;
			}
			else if(a[u].f2+1<=a[v].f2&&a[u].f2+1>a[v].f3)
			{
				a[v].f3=a[u].f2+1;
//				a[v].g3=u;
			}
		}
		else if(v==a[u].g2)
		{
			if(v==a[u].dpg1)
			{
				ans=max(ans,max(max((a[u].f1+a[u].f3)*a[v].dpf1,a[u].dpf2*a[v].dpf1),max((a[u].f1+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf2*(a[v].f1+a[v].f2))));
				if(max(a[u].dpf2,a[u].f1+a[u].f3)>a[v].dpf1)
				{
					a[v].dpf2=a[v].dpf1;
//					a[v].dpg2=a[v].dpg1;
					a[v].dpf1=max(a[u].dpf2,a[u].f1+a[u].f3);
					a[v].dpg1=u;
				}
				else if(max(a[u].dpf2,a[u].f1+a[u].f3)<=a[v].dpf1&&max(a[u].dpf2,a[u].f1+a[u].f3)>a[v].dpf2)
				{
					a[v].dpf2=max(a[u].dpf2,a[u].f1+a[u].f3);
//					a[v].dpg2=u;
				}
			}
			else
			{
				ans=max(ans,max(max((a[u].f1+a[u].f3)*a[v].dpf1,a[u].dpf1*a[v].dpf1),max((a[u].f1+a[u].f3)*(a[v].f1+a[v].f2),a[u].dpf1*(a[v].f1+a[v].f2))));
				if(max(a[u].dpf1,a[u].f1+a[u].f3)>a[v].dpf1)
				{
					a[v].dpf2=a[v].dpf1;
//					a[v].dpg2=a[v].dpg1;
					a[v].dpf1=max(a[u].dpf1,a[u].f1+a[u].f3);
					a[v].dpg1=u;
				}
				else if(max(a[u].dpf1,a[u].f1+a[u].f3)<=a[v].dpf1&&max(a[u].dpf1,a[u].f1+a[u].f3)>a[v].dpf2)
				{
					a[v].dpf2=max(a[u].dpf1,a[u].f1+a[u].f3);
//					a[v].dpg2=u;
				}
			}
			if(a[u].f1+1>a[v].f1)
			{
				a[v].f3=a[v].f2;
//				a[v].g3=a[v].g2;
				a[v].f2=a[v].f1;
				a[v].g2=a[v].g1;
				a[v].f1=a[u].f1+1;
				a[v].g1=u;
			}
			else if(a[u].f1+1<=a[v].f1&&a[u].f1+1>a[v].f2)
			{
				a[v].f3=a[v].f2;
//				a[v].g3=a[v].g2;
				a[v].f2=a[u].f1+1;
				a[v].g2=u;
			}
			else if(a[u].f1+1<=a[v].f2&&a[u].f1+1>a[v].f3)
			{
				a[v].f3=a[u].f1+1;
//				a[v].g3=u;
			}
		}
		else
		{
			if(v==a[u].dpg1)
			{
				ans=max(ans,max(max((a[u].f1+a[u].f2)*a[v].dpf1,a[u].dpf2*a[v].dpf1),max((a[u].f1+a[u].f2)*(a[v].f1+a[v].f2),a[u].dpf2*(a[v].f1+a[v].f2))));
				if(max(a[u].dpf2,a[u].f1+a[u].f2)>a[v].dpf1)
				{
					a[v].dpf2=a[v].dpf1;
//					a[v].dpg2=a[v].dpg1;
					a[v].dpf1=max(a[u].dpf2,a[u].f1+a[u].f2);
					a[v].dpg1=u;
				}
				else if(max(a[u].dpf2,a[u].f1+a[u].f2)<=a[v].dpf1&&max(a[u].dpf2,a[u].f1+a[u].f2)>a[v].dpf2)
				{
					a[v].dpf2=max(a[u].dpf2,a[u].f1+a[u].f2);
//					a[v].dpg2=u;
				}
			}
			else
			{
				ans=max(ans,max(max((a[u].f1+a[u].f2)*a[v].dpf1,a[u].dpf1*a[v].dpf1),max((a[u].f1+a[u].f2)*(a[v].f1+a[v].f2),a[u].dpf1*(a[v].f1+a[v].f2))));
				if(max(a[u].dpf1,a[u].f1+a[u].f2)>a[v].dpf1)
				{
					a[v].dpf2=a[v].dpf1;
//					a[v].dpg2=a[v].dpg1;
					a[v].dpf1=max(a[u].dpf1,a[u].f1+a[u].f2);
					a[v].dpg1=u;
				}
				else if(max(a[u].dpf1,a[u].f1+a[u].f2)<=a[v].dpf1&&max(a[u].dpf1,a[u].f1+a[u].f2)>a[v].dpf2)
				{
					a[v].dpf2=max(a[u].dpf1,a[u].f1+a[u].f2);
//					a[v].dpg2=u;
				}
			}
			if(a[u].f1+1>a[v].f1)
			{
				a[v].f3=a[v].f2;
//				a[v].g3=a[v].g2;
				a[v].f2=a[v].f1;
				a[v].g2=a[v].g1;
				a[v].f1=a[u].f1+1;
				a[v].g1=u;
			}
			else if(a[u].f1+1<=a[v].f1&&a[u].f1+1>a[v].f2)
			{
				a[v].f3=a[v].f2;
//				a[v].g3=a[v].g2;
				a[v].f2=a[u].f1+1;
				a[v].g2=u;
			}
			else if(a[u].f1+1<=a[v].f2&&a[u].f1+1>a[v].f3)
			{
				a[v].f3=a[u].f1+1;
//				a[v].g3=u;
			}
		}
		dfs2(v,u);
	}
	return ;
}
signed main()
{
	n=qread();
	for(re int i=1;i<n;i++)
	{
		int u=qread();
		int v=qread();
		mr(u,v);
		mr(v,u);
	}
	dfs1(1,0);
//	for(re int i=1;i<=n;i++)
//	{
//		cout<<"i="<<i<<" "<<a[i].dpf1<<" "<<a[i].dpg1<<" "<<a[i].dpf2<<" "<<a[i].dpg2<<" "<<a[i].f1<<" "<<a[i].g1<<" "<<a[i].f2<<" "<<a[i].g2<<" "<<a[i].f3<<" "<<a[i].g3<<"\n";
//	}
	dfs2(1,0);
	qwrite(ans);
	putchar('\n');
	return 0;
}

祝大家 \(AC\) 愉快^_^