给出一颗nn个点的树,树上随机分配00n1n-1 的边权,不存在权值相同的两条边。

定义mex(u,v)mex(u,v)为:树上uuvv的简单路径中所有边权的mexmex。 求

1uvnmex(u,v) \sum_{1\leq u\leq v\leq n}mex(u,v)

n3000n \le 3000

CF1293E

Solution

考虑从小到大填入权值, 发现mexmex这个限制其实很紧,只要没经过00边的路径答案都是00,剩下路径中只要没经过11边的路径答案都是11$\dots$

即对答案产生贡献的边最后只会在一条链上,且一定是一段值域上的前缀,且每次在链的两段填入新的权值是更优的。

考虑对每条链DP出答案,设dp(x,y)dp(x, y)表示(x,y)(x, y)这条链的答案,size(x,y)size(x, y)表示以xx为根时yysizesizefa(x,y)fa(x, y)表示以xx为根时yy的父亲

转移很简单:

dp(x,y)=max{dp(fa(y,x),y),dp(x,fa(x,y))}+size(x,y)size(y,x) dp(x, y) = \max \{dp\Big(fa(y, x), y\Big), dp\Big(x, fa(x, y)\Big)\} + size(x, y) * size(y, x)

记忆化搜索实现

Code

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
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 3000;

int N, e, Begin[MAXN + 5], To[MAXN * 2 + 5], Next[MAXN * 2 + 5];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

int size[MAXN + 5][MAXN + 5], fa[MAXN + 5][MAXN + 5];

inline void dfs (int x, int f, int s)
{
size[s][x] = 1;
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (y == f) continue;
fa[s][y] = x;
dfs (y, x, s);
size[s][x] += size[s][y];
}
}

LL Dp[MAXN + 5][MAXN + 5];

inline LL get_dp (int x, int y)
{
if (~Dp[x][y]) return Dp[x][y];
if (!x || !y || x == y) return Dp[x][y] = 0;
Dp[x][y] = max (get_dp (fa[y][x], y), get_dp (x, fa[x][y])) + (LL) size[y][x] * size[x][y];
return Dp[x][y];
}

inline void Solve ()
{
memset (Dp, -1, sizeof Dp);
for (int i = 1; i <= N; ++i) dfs (i, 0, i);

LL ans = 0;
for (int i = 1; i <= N; ++i) for (int j = i + 1; j <= N; ++j) Chkmax (ans, get_dp (i, j));
cout << ans << endl;
}

inline void Input ()
{
N = read<int>();
for (int i = 1; i < N; ++i)
{
int x = read<int>(), y = read<int>();
add_edge (x, y);
add_edge (y, x);
}
}

int main ()
{

#ifdef hk_cnyali
freopen("E.in", "r", stdin);
freopen("E.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}