CF1179D-Fedor Runs for President

题目:

题目描述:

Fedor runs for president of Byteland! In the debates, he will be asked how to solve Byteland’s transport problem. It’s a really hard problem because of Byteland’s transport system is now a tree (connected graph without cycles). Fedor’s team has found out in the ministry of transport of Byteland that there is money in the budget only for one additional road. In the debates, he is going to say that he will build this road as a way to maximize the number of distinct simple paths in the country. A simple path is a path which goes through every vertex no more than once. Two simple paths are named distinct if sets of their edges are distinct.

But Byteland’s science is deteriorated, so Fedor’s team hasn’t succeeded to find any scientists to answer how many distinct simple paths they can achieve after adding exactly one edge on the transport system?

Help Fedor to solve it.

An edge can be added between vertices that are already connected, but it can’t be a loop.

In this problem, we consider only simple paths of length at least two.

输入格式:

The first line contains one integer $ n $ ( $ 2 \leq n \leq 500\ 000 $ ) — number of vertices in Byteland’s transport system.

Each of the following $ n - 1 $ lines contains two integers $ v_i $ and $ u_i $ ( $ 1 \leq v_i, u_i \leq n $ ). It’s guaranteed that the graph is tree.

输出格式:

Print exactly one integer — a maximal number of simple paths that can be achieved after adding one edge.

样例:

样例输入 1:

1
2
3

2
1 2

样例输出 1:

1
2

2

样例输入 2:

1
2
3
4
5

4
1 2
1 3
1 4

样例输出 2:

1
2

11

样例输入 3:

1
2
3
4
5
6
7

6
1 2
1 3
3 4
3 5
4 6

样例输出 3:

1
2

29

思路:

这是一道斜率优化 dp 题，所以我们不用斜率优化做。/kk

首先我们肯定是先一条链加上一条边形成一个环。

将答案容斥变成$n*(n-1)-\sum\limits_{i=1}^{L}\frac{s_{a_i}\times (s_{a_i}-1)}{2}$

我们要让答案最大即最小化$\sum\limits_{i=1}^{L}\frac{s_{a_i}\times (s_{a_i}-1)}{2}$

之前有一位大佬在题解中提到了一个性质，即我们像求直径一样求就行了。但似乎没有给出证明。所以我自己YY了一个。

考虑两个点$x$,$y$ 在以1为根dfs时$x$比$y$优，则不存在一个点$z$使得$(y,z)$是我们要找的那条连。

显然$x$,$y$是两个叶子节点。

令$l=lca(x,y)$，很显然

当$z$不在以$l$为根的子树内时$(x,z)$比$(y,z)$要优。

当z在以$l$为根的子树内时$(x,y)$比$(y,z)$更优。

所以不存在一个$z$使得$(y,z)$是最优解。

实现:

 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

#include "ybwhead/ios.h"
int n;
const int maxn = 5e5 + 10;
struct edge
{
    int v, nxt;
} e[maxn << 1];
int head[maxn], tot;
void __ADD(int u, int v)
{
    e[++tot].v = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}
void add(int u, int v)
{
    __ADD(u, v);
    __ADD(v, u);
}
long long ans[maxn];
long long siz[maxn];
void pd(int u, int fa)
{
    siz[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        pd(v, u);
        siz[u] += siz[v];
    }
}
void dfs(int u, int fa)
{
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        ans[v] = ans[u] + 1ll * (siz[u] - siz[v]) * siz[v];
        dfs(v, u);
    }
}
int main()
{
    yin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        yin >> u >> v;
        add(u, v);
    }
    pd(1, 0);
    ans[1] = 1ll * n * (n - 1) / 2;
    dfs(1, 0);
    int an = 0;
    for (int i = 1; i <= n; i++)
        if (ans[an] < ans[i])
            an = i;
    pd(an, 0);
    ans[an] = ans[1];
    dfs(an, 0);
    an = 0;
    for (int i = 1; i <= n; i++)
        if (ans[an] < ans[i])
            an = i;
    yout << ans[an] << endl;
    return 0;
}