#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5;
int sizee[MAX_N + 1], depth[MAX_N + 1], pairr[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int n;
int c;
void findCentroid( int u, int p ) {
int maxSizee = 0;
sizee[u] = 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
findCentroid( v, u );
sizee[u] += sizee[v];
maxSizee = max( maxSizee, sizee[v] );
}
maxSizee = max( maxSizee, n - sizee[u] );
if ( maxSizee <= n / 2 )
c = u;
}
void calcSizes( int u, int p ) {
sizee[u] = 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
calcSizes( v, u );
sizee[u] += sizee[v];
}
}
long long maxSumDist;
vector<int> vert;
vector<int> vertStack;
void dfs( int u, int p ) {
vert.push_back( u );
depth[u] = depth[p] + 1;
for ( int v: adj[u] ) {
if ( v == p )
continue;
dfs( v, u );
}
}
int main() {
cin >> n;
for ( int i = 0; i < n - 1; i++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
}
findCentroid( 1, 0 );
calcSizes( c, 0 );
sort( adj[c].begin(), adj[c].end(), []( int u, int v ) {
return sizee[u] > sizee[v];
} );
maxSumDist = 0;
for ( int u: adj[c] ) {
vert.clear();
dfs( u, c );
vector<int> add;
for ( int v: vert ) {
if ( !vertStack.empty() ) {
pairr[v] = vertStack.back();
pairr[vertStack.back()] = v;
vertStack.pop_back();
} else
add.push_back( v );
maxSumDist += depth[v];
}
for ( int v: add )
vertStack.push_back( v );
}
if ( vertStack.empty() ) {
int a = adj[c][0], b = pairr[a];
pairr[a] = b;
pairr[b] = c;
pairr[c] = a;
} else {
pairr[c] = vertStack.back();
pairr[vertStack.back()] = c;
vertStack.pop_back();
}
cout << 0 << " " << 2 * maxSumDist << "\n";
for ( int v = 1; v <= n; v++ )
cout << v << " ";
cout << "\n";
for ( int v = 1; v <= n; v++ )
cout << pairr[v] << " ";
cout << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
2 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
3 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
4 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
5 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
6 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
7 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
8 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
9 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
10 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
11 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
12 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
13 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
14 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
15 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
16 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
17 |
Partially correct |
1 ms |
2904 KB |
Partially correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2652 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 256] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
2 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
3 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
4 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
5 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
6 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
7 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
8 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
9 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
10 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
11 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
12 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
13 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
14 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
15 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
16 |
Partially correct |
1 ms |
2652 KB |
Partially correct |
17 |
Partially correct |
1 ms |
2904 KB |
Partially correct |
18 |
Incorrect |
1 ms |
2652 KB |
Integer parameter [name=vi] equals to 0, violates the range [1, 256] |
19 |
Halted |
0 ms |
0 KB |
- |