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
| #include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 50;
vector< int > adj[maxn];
int distA[maxn], distB[maxn];
int pre[maxn];
bool is_path[maxn];
vector< int > path;
int nodeA, nodeB;
int n;
struct Op { int u, v, rem; };
vector< Op > ops;
ll ans;
int bfs( int start, int dist[], bool flag )
{
for( int i = 1; i <= n; ++ i ) dist[i] = -1;
if( flag ) {
for( int i = 1; i <= n; ++ i ) pre[i] = 0;
}
queue< int > q;
q.push( start );
dist[start] = 0;
int root = start;
while( !q.empty( ) )
{
int u = q.front( );
q.pop( );
if( dist[u] > dist[root] ) root = u;
for( int v : adj[u] )
{
if( dist[v] == -1 )
{
dist[v] = dist[u] + 1;
if( flag ) pre[v] = u;
q.push( v );
}
}
}
return root;
}
void dfs( int u, int fa )
{
for( int v : adj[u] )
{
if( v == fa || is_path[v] ) continue;
dfs( v, u );
}
if( distA[u] > distB[u] )
{
ans += distA[u];
ops.push_back({ nodeA, u, u });
}
else
{
ans += distB[u];
ops.push_back({ nodeB, u, u });
}
}
int main( )
{
cin >> n;
for( int i = 1; i < n; ++ i )
{
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
}
nodeA = bfs( 1, distA, 0 );
nodeB = bfs( nodeA, distA, 1 );
bfs( nodeB, distB, 0 );
int cur = nodeB;
while( cur != 0 )
{
is_path[cur] = 1;
path.push_back( cur );
cur = pre[cur];
}
for( int u : path )
{
for( int v : adj[u] )
{
if( !is_path[v] )
{
dfs( v, u );
}
}
}
for( int i = 0; i < path.size( ) - 1; ++ i )
{
int u = path[i];
ans += distA[u];
ops.push_back( { nodeA, u, u } );
}
cout << ans << '\n';
for( auto [u, v, rmv] : ops )
{
cout << u << " " << v << " " << rmv << '\n';
}
return 0;
}
|