算法-DP-专题练习

发表于 更新于

目前共计 16 道题

最长公共上升子序列-线性DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;

int a[N], b[N];
int f[N][N]; // end in b[j]

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        int val = 0; // val = f[i - 1][0] = 0
        for (int j = 1; j <= n; ++j)
        {
            if (a[i] != b[j])
                f[i][j] = f[i - 1][j];
            else
                f[i][j] = val + 1;
            if (a[i] > b[j])
                val = max(val, f[i - 1][j]);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i)
        res = max(res, f[n][i]);
    cout << res << endl;
}

移动服务-线性DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 2e2 + 10;

int n, m;
int a[M][M];
int f[N][M][M]; // 完成了第 i 个请求，一个人在 p[i]，另外两个人在 j, k 位置
int p[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> a[i][j];
    for (int i = 1; i <= m; ++i)
        cin >> p[i];
    p[0] = 3;
    memset(f, 0x3f, sizeof(f));
    f[0][1][2] = 0; //
    for (int i = 0; i < m; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
            {
                if (j == k || k == p[i] || p[i] == j)
                    continue;
                f[i + 1][j][k] = min(f[i + 1][j][k], f[i][j][k] + a[p[i]][p[i + 1]]);    // move 3
                f[i + 1][p[i]][k] = min(f[i + 1][p[i]][k], f[i][j][k] + a[j][p[i + 1]]); // move 2
                f[i + 1][j][p[i]] = min(f[i + 1][j][p[i]], f[i][j][k] + a[k][p[i + 1]]); // move 1
            }
    int res = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (p[m] != i && i != j && p[m] != j)
                res = min(res, f[m][i][j]);
    cout << res << endl;
}

混合背包-01背包+完全背包+多重背包

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if (s == -1)
        {
            for (int j = m; j >= v; j--)
                f[j] = max(f[j], f[j - v] + w);
        }
        else if (s == 0)
        {
            for (int j = v; j <= m; j++)
                f[j] = max(f[j], f[j - v] + w);
        }
        else
        {
            int sg = 1;
            while (sg <= s)
            {
                for (int j = m; j >= sg * v; j--)
                    f[j] = max(f[j], f[j - sg * v] + sg * w);
                s -= sg;
                sg *= 2;
            }
            if (s > 0)
            {
                for (int j = m; j >= s * v; j--)
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    cout << f[m];
}

多边形

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
#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int n;
int dpmax[N][N];
int dpmin[N][N];
int a[N];
char op[N]; // op[i+1]表示a[i]与a[i+1]计算的符号

int main()
{
    memset(dpmax, 0x80, sizeof(dpmax));
    memset(dpmin, 0x3f, sizeof(dpmin));
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> op[i] >> a[i], op[i + n] = op[i], a[i + n] = a[i];

    for (int i = 1; i <= 2 * n; ++i)
        dpmin[i][i] = dpmax[i][i] = a[i];

    for (int len = 1; len < n; ++len)
    {
        for (int i = 1; i + len <= 2 * n; ++i)
        {
            int j = i + len;
            for (int p = i; p < j; ++p)
            {
                if (op[p + 1] == 't')
                {
                    dpmin[i][j] = min(dpmin[i][j], dpmin[i][p] + dpmin[p + 1][j]);
                    dpmax[i][j] = max(dpmax[i][j], dpmax[i][p] + dpmax[p + 1][j]);
                }
                else
                {
                    dpmax[i][j] = max(dpmax[i][j], dpmax[i][p] * dpmax[p + 1][j]);
                    dpmax[i][j] = max(dpmax[i][j], dpmax[i][p] * dpmin[p + 1][j]);
                    dpmax[i][j] = max(dpmax[i][j], dpmin[i][p] * dpmax[p + 1][j]);
                    dpmax[i][j] = max(dpmax[i][j], dpmin[i][p] * dpmin[p + 1][j]);
                    dpmin[i][j] = min(dpmin[i][j], dpmin[i][p] * dpmin[p + 1][j]);
                    dpmin[i][j] = min(dpmin[i][j], dpmax[i][p] * dpmin[p + 1][j]);
                    dpmin[i][j] = min(dpmin[i][j], dpmin[i][p] * dpmax[p + 1][j]);
                    dpmin[i][j] = min(dpmin[i][j], dpmax[i][p] * dpmax[p + 1][j]);
                }
            }
        }
    }
    int res = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
        res = max(dpmax[i][i + n - 1], res);
    cout << res << endl;
    for (int i = 1; i <= n; i++)
        if (dpmax[i][i + n - 1] == res)
            cout << i << " ";
}

选课-分组背包+树形DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 310;

int n, m;
int head[N], ne[N], edge[N], tot = 0;
int val[N];
int f[N][N];

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

void dp(int x)
{
    f[x][0] = 0;
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        dp(y);
        for (int j = m; j >= 0; --j)
            for (int k = 1; k <= j; ++k)
                f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
    }
    if (x != 0)
        for (int i = m; i >= 1; --i)
            f[x][i] = f[x][i - 1] + val[x];
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x >> val[i];
        add(x, i);
    }
    dp(0);
    cout << f[0][m];
}

乌龟棋-线性DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 355, M = 42;

int n, m;
int a[N];
int b[5];          // 表示前进 i 步的卡片个数
int f[M][M][M][M]; // 分别使用了 i j k l 张卡之后，获得的最大值
bool vis[N];       // 是否已确定其最大值

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= m; ++i)
    {
        int x;
        cin >> x;
        b[x]++;
    }
    f[0][0][0][0] = a[1];
    for (int i = 0; i <= b[1]; ++i)
        for (int j = 0; j <= b[2]; ++j)
            for (int k = 0; k <= b[3]; ++k)
                for (int l = 0; l <= b[4]; ++l)
                {
                    int v = a[1 + i + j * 2 + k * 3 + l * 4];
                    int &x = f[i][j][k][l];
                    if (i > 0)
                        x = max(x, f[i - 1][j][k][l] + v);
                    if (j > 0)
                        x = max(x, f[i][j - 1][k][l] + v);
                    if (k > 0)
                        x = max(x, f[i][j][k - 1][l] + v);
                    if (l > 0)
                        x = max(x, f[i][j][k][l - 1] + v);
                }
    cout << f[b[1]][b[2]][b[3]][b[4]];
}

花店橱窗-线性DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int n, m;
int v[N][N];
int f[N][N]; // 前 i 朵花放在前 j 个花瓶里

void output(int i, int j)
{
    if (i == 0)
        return;
    while (f[i][j] == f[i][j - 1])
        j--;
    output(i - 1, j - 1);
    cout << j << " ";
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> v[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= m; ++j)
        {
            if (j == i)
                f[i][j] = f[i - 1][j - 1] + v[i][j];
            else
                f[i][j] = max(f[i][j - 1], f[i - 1][j - 1] + v[i][j]);
        }
    cout << f[n][m] << endl;
    output(n, m);
}

Buy Low Buy Lower-线性DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;

int n;
int a[N];
int f[N]; // 最后一个数字是 a[i]时，下降子序列的长度
int c[N]; // 方案数

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int res = 0, cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        f[i] = 1;
        for (int j = i - 1; j >= 1; j--)
            if (a[j] > a[i])
                f[i] = max(f[j] + 1, f[i]);
        for (int j = i - 1; j >= 1; j--)
            if (f[j] == f[i] && a[j] == a[i])
                c[j] = 0;
            else if (f[j] + 1 == f[i] && a[j] > a[i])
                c[i] += c[j];
        res = max(f[i], res);
        if (f[i] == 1)
            c[i] = 1;
    }

    for (int i = 1; i <= n; ++i)
        if (res == f[i])
            cnt += c[i];
    cout << res << " " << cnt;
}

金明的预算方案-分组背包

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
#include <bits/stdc++.h>
using namespace std;
const int N = 3.2e4 + 10, M = 62;

int m, n;
vector<int> atta[N];
int v[N], p[N], q[N]; // 0 表示主件
int f[M][N];          // 只考虑前 i 个物品但是包括每个物品的附件。遇到附件则跳过

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> v[i] >> p[i] >> q[i];
        if (q[i] != 0)
            atta[q[i]].push_back(i);
    }
    for (int i = 1; i <= n; ++i)
    {
        if (q[i])
        {
            for (int j = 0; j <= m; j++)
                f[i][j] = f[i - 1][j];
        }
        else
        {
            if (atta[i].size() == 0)
            {
                for (int j = 0; j < v[i]; j++)
                    f[i][j] = f[i - 1][j];
                for (int j = v[i]; j <= m; j++)
                    f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + v[i] * p[i]);
            }
            else if (atta[i].size() == 1)
            {
                for (int k = 0; k < 2; k++)
                {
                    int tv = v[i] + (k & 1) * v[atta[i][0]];
                    int tw = v[i] * p[i] + (k & 1) * v[atta[i][0]] * p[atta[i][0]];
                    for (int j = 0; j < tv; j++)
                        f[i][j] = max(f[i][j], f[i - 1][j]);
                    for (int j = tv; j <= m; j++)
                        f[i][j] = max(f[i][j], max(f[i - 1][j], f[i - 1][j - tv] + tw));
                }
            }
            else
            {
                for (int k = 0; k < 4; k++)
                {
                    int tv = v[i] + bool(k & 1) * v[atta[i][0]] + bool(k & 2) * v[atta[i][1]];
                    int tw = v[i] * p[i] + bool(k & 1) * v[atta[i][0]] * p[atta[i][0]] + bool(k & 2) * v[atta[i][1]] * p[atta[i][1]];
                    for (int j = 0; j < tv; j++)
                        f[i][j] = max(f[i][j], f[i - 1][j]);
                    for (int j = tv; j <= m; j++)
                        f[i][j] = max(f[i][j], max(f[i - 1][j], f[i - 1][j - tv] + tw));
                }
            }
        }
    }
    cout << f[n][m];
}

金字塔-区间DP

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e2 + 10, MOD = 1e9;

char s[N];
ll f[N][N]; // f[i][j] 表示 i ~ j 闭区间构成的子树的可能结构数量

ll solve(int l, int r)
{
    if (l > r)
        return 0;
    if (l == r)
        return f[l][r] = 1;
    if (f[l][r] != -1)
        return f[l][r];
    f[l][r] = 0;
    if (s[l] != s[r])
        return 0;
    for (int i = l + 2; i <= r; i++)
    {
        if (s[i] == s[l])
        {
            solve(l + 1, i - 1);
            solve(i, r);
            f[l][r] = (f[l][r] + f[l + 1][i - 1] * f[i][r]) % MOD;
        }
    }
    return f[l][r];
}

int main()
{
    memset(f, -1, sizeof(f));
    cin >> (s + 1);
    int r = strlen(s + 1);
    solve(1, r);
    cout << f[1][r];
}

树的中心-树形DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 2 * N;

int n;
int head[N], edge[M], ne[M], weight[M], tot = 1;
int d1[N], d2[N], p1[N];
int up[N];

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

void dfs_1(int u, int p = -1)
{
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        if (v == p)
            continue;
        dfs_1(v, u);
        if (d1[v] + weight[i] >= d1[u])
        {
            d2[u] = d1[u];
            d1[u] = d1[v] + weight[i];
            p1[u] = v;
        }
        else if (d1[v] + weight[i] > d2[u])
            d2[u] = d1[v] + weight[i];
    }
}

void dfs_2(int u, int p = -1)
{
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        if (v == p)
            continue;
        if (p1[u] == v)
            up[v] = max(up[u], d2[u]) + weight[i];
        else
            up[v] = max(up[u], d1[u]) + weight[i];
        dfs_2(v, u);
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dfs_1(1, -1);
    dfs_2(1, -1);
    int res = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i)
        res = min(res, max(up[i], d1[i]));
    cout << res;
}

数字转换-树形DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, M = 2 * N;

int n;
int head[N], edge[M], ne[M], tot = 1;
int fsum[N];    // i 的约数之和的大小
int d[N], f[N]; // 以 i 为根到叶节点的最大距离，与经过 i 点的最长路

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

void dfs(int u, int p = -1)
{
    if (d[u] != -1)
        return;
    d[u] = 0;
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        if (v == p)
            continue;
        dfs(v, u);
        f[u] = max(f[u], d[u] + d[v] + 1);
        d[u] = max(d[u], d[v] + 1);
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    memset(d, -1, sizeof(d));
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 2; j * i <= n; ++j) // 从 2 开始：这个数本身不算
            fsum[i * j] += i;
    for (int i = 2; i <= n; i++)
        if (fsum[i] < i)
        {
            add(fsum[i], i);
            add(i, fsum[i]);
        }
    for (int i = 1; i <= n; ++i)
        dfs(i);
    int res = 0;
    for (int i = 1; i <= n; ++i)
        res = max(res, f[i]);
    cout << res;
}

二叉苹果树-有依赖的背包

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
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 2 * N;

int n, m;
int f[N][N]; // 以 i 为子树，保留了 j 个树枝的苹果最大值
int a[N];    // 苹果数量

int head[N], ne[M], edge[M], weight[M], tot = 1;

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

void dp(int u, int p = -1)
{
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i], w = weight[i];
        if (v == p)
            continue;
        dp(v, u);
        for (int j = m; j >= 0; j--)    
            for (int k = 0; k < j; k++)
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + w);
    }
}

int main()
{
    memset(head, -1, sizeof(head));

    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dp(1);
    cout << f[1][m];
}

休息时间-环形DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 4010;

int n, m;
int f[2][N][2]; // 在第 i 个小时，已经睡了 j 小时, 第 i 个小时是否在休息
int a[N];

int main()
{
    memset(f, 0x80, sizeof(f));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    f[1][0][0] = 0;
    f[1][1][1] = 0;
    int res = 0;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= min(m, i); j++)
        {
            f[i & 1][j][0] = max(f[(i + 1) & 1][j][0], f[(i + 1) & 1][j][1]);
            if (j > 0)
                f[i & 1][j][1] = max(f[(i + 1) & 1][j - 1][0], f[(i + 1) & 1][j - 1][1] + a[i]);
        }
    res = max(f[1 & n][m][0], f[1 & n][m][1]);
    memset(f, 0x80, sizeof(f));
    f[1][1][1] = a[1];
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= min(m, i); j++)
        {
            f[i & 1][j][0] = max(f[(i + 1) & 1][j][0], f[(i + 1) & 1][j][1]);
            if (j > 0)
                f[i & 1][j][1] = max(f[(i + 1) & 1][j - 1][0], f[(i + 1) & 1][j - 1][1] + a[i]);
        }
    res = max(res, f[1 & n][m][1]);
    cout << res << endl;
}

Mondriaan’s dream-状态压缩DP

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
#include <bits/stdc++.h>
using namespace std;
const int N = 12;

int n, m;
long long f[N][1 << N];
bool ez[1 << N];

int main()
{
    while (cin >> n >> m)
    {
        if (n == 0)
            break;
        for (int i = 0; i < (1 << m); i++)
        {
            bool cnt = false, has_odd = false;
            for (int j = 0; j < m; j++)
            {
                if ((i >> j) & 1)
                    has_odd |= cnt, cnt = 0;
                else
                    cnt = !cnt;
            }
            ez[i] = !(has_odd || cnt);
        }
        f[0][0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < (1 << m); j++)
            {
                f[i][j] = 0;
                for (int k = 0; k < (1 << m); k++)
                    if (!(j & k) && ez[j | k])
                        f[i][j] += f[i - 1][k];
            }
        }
        cout << f[n][0] << endl;
    }
}

Sum of Distances in Tree-换根DP

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
func sumOfDistancesInTree(n int, edges [][]int) []int {
	adjs := make([][]int, n)
	for i := range adjs {
		adjs[i] = make([]int, 0)
	}
	for i := range edges {
		adjs[edges[i][0]] = append(adjs[edges[i][0]], edges[i][1])
		adjs[edges[i][1]] = append(adjs[edges[i][1]], edges[i][0])
	}
	dp, sz := make([]int, n), make([]int, n)
	var dfs func(u, p int)
	dfs = func(u, p int) {
		sz[u]++
		for _, v := range adjs[u] {
			if v == p {
				continue
			}
			dfs(v, u)
			dp[u] += dp[v] + sz[v]
			sz[u] += sz[v]
		}
	}
	dfs(0, -1)
	var change func(u, p int)
	ans := make([]int, n)
	change = func(u, p int) {
		// root is u, and switch to v
		ans[u] = dp[u]
		for _, v := range adjs[u] {
			if p == v {
				continue
			}
			dp[u] -= dp[v] + sz[v]
			sz[u] -= sz[v]
			sz[v] += sz[u]
			dp[v] += dp[u] + sz[u]
			change(v, u)
			dp[v] -= dp[u] + sz[u]
			sz[v] -= sz[u]
			sz[u] += sz[v]
			dp[u] += dp[v] + sz[v]
		}
	}
	change(0, -1)
	return ans
}