「AGC018D」Tree and Hamilton Path

发表于 分类于

$Link$

给你一棵 $n$ 个点的树，每条边有权值 $c_i$ 。现在你要找到 $n$ 的一个排列，使得按照这个顺序访问每个点，所经过的路径长度最大（也即最长的曼哈顿路径）。

$2\le n\le10^5,1\le c_i\le10^8$。

先考虑曼哈顿回路怎么做。

首先很显然地，一条边被经过的次数的上界为这条边两端的点的数量的较小值（在两个部分反复横跳即可）。

考虑如何同时取到每条边的上界，绕着树的重心，在各个子树之间反复横跳即可。

如果有两个重心，显然是在两个部分之间反复横跳最优。

接下来考虑曼哈顿路径怎么做，其实就是在回路上去掉两个点间的路径，最小化这条路径。

稍加思考可以知道，如果只有一个重心，即为重心周围最小的一条边；如果有两个重心，只能割掉两个重心之间的边。

时间复杂度 $O(n)$，代码中的计算方式有点奇怪。

$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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define ll long long
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 1e5;

int n;
struct Edge {
    int to, next, w;
} edge[(N << 1) + 1];
int start[N + 1], tot;
int sz[N + 1];
ll dis[N + 1];
int root;
bool flag = false;
ll ans, minn = 1e18;

inline void addedge(int u, int v, int w)
{
    edge[++tot] = { v, start[u], w };
    start[u] = tot;
    edge[++tot] = { u, start[v], w };
    start[v] = tot;
    return;
}
inline void dfs(int u, int fa)
{
    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa) {
            dis[v] = dis[u] + edge[i].w;
            dfs(v, u);
        }
    }
}
inline void dfs1(int u, int fa)
{
    sz[u] = 1;
    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa) {
            dfs1(v, u);
            if (flag) {
                if (v == root)
                    ans -= edge[i].w;
                return;
            }
            sz[u] += sz[v];
        }
    }
    if (sz[u] == n / 2) {
        root = u;
        flag = true;
    }
    return;
}
inline void dfs2(int u, int fa)
{
    sz[u] = 1;
    int maxx = 0;

    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa) {
            dfs2(v, u);
            if (flag)
                return;
            maxx = max(maxx, sz[v]);
            sz[u] += sz[v];
        }
    }
    maxx = max(maxx, n - sz[u]);
    if (maxx <= (n >> 1)) {
        root = u;
        flag = true;
    }
    return;
}
int main()
{
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(), w = read();
        addedge(u, v, w);
    }

    if ((n & 1) == 0) {
        dfs1(1, 0);
        if (root) {
            dfs(root, 0);
            for (int i = 1; i <= n; i++)
                ans += 2 * dis[i];
            printf("%lld\n", ans);
            return 0;
        }
    }
    dfs2(1, 0);
    dfs(root, 0);
    for (int i = 1; i <= n; i++) {
        if (i != root) {
            ans += 2 * dis[i];
            minn = min(minn, dis[i]);
        }
    }
    ans -= minn;

    printf("%lld\n", ans);
    return 0;
}