#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
int N, md, fn, st, rt, sz[200005], osz[200005];
bool on_path[200005];
vector<int> path, adj[200005];
multiset<int> poss[200005];
priority_queue<ii, vector<ii>, greater<ii> > pq[200005];
void get_diam(int n, int e = -1, int d = 0) {
if (d > md) {
md = d;
fn = n;
}
for (auto u : adj[n]) if (u != e) get_diam(u, n, d + 1);
}
bool get_path(int n, int e = -1) {
if (n == fn) {
on_path[n] = 1;
path.pb(n);
return 1;
}
for (auto u : adj[n]) if (u != e)
if (get_path(u, n)) {
on_path[n] = 1;
path.pb(n);
return 1;
}
return 0;
}
int dfs(int n, int e = -1, int d = 0) {
sz[n] = 1;
for (auto u : adj[n]) if (u != e)
sz[n] += dfs(u, n);
pq[rt].emplace(sz[n], d);
poss[rt].insert(d);
return sz[n];
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1, u, v; i < N; i++) {
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
md = -1;
get_diam(1);
md = -1;
st = fn;
get_diam(st);
// diameter is st --> fn
get_path(st);
for (int i = 1; i <= N; i++)
if (on_path[i]) {
sz[i] = 1;
rt = i;
for (auto u : adj[i])
if (!on_path[u]) sz[i] += dfs(u, i);
pq[i].emplace(sz[i], 0);
poss[i].insert(0);
osz[i] = sz[i];
}
reverse(path.begin(), path.end());
for (int k = 1, ptr = 0, ptr2 = (int)path.size() - 1; k <= N; k++) {
if (k & 1) cout << "1\n";
else {
if (sz[path[ptr]] == 0) ptr++;
sz[path[ptr]]--;
if (sz[path[ptr2]] == 0) ptr2--;
sz[path[ptr2]]--;
while (pq[path[ptr]].top().first < osz[path[ptr]] - sz[path[ptr]]) {
poss[path[ptr]].erase(poss[path[ptr]].find(pq[path[ptr]].top().second));
pq[path[ptr]].pop();
}
while (pq[path[ptr2]].top().first < osz[path[ptr2]] - sz[path[ptr2]]) {
poss[path[ptr2]].erase(poss[path[ptr2]].find(pq[path[ptr2]].top().second));
pq[path[ptr2]].pop();
}
cout << ptr2 - ptr + 1 + *poss[path[ptr]].rbegin() + *poss[path[ptr2]].rbegin() << '\n';
}
}
}
Compilation message
meetings2.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
67 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 3 |
Correct |
11 ms |
20596 KB |
Output is correct |
| 4 |
Correct |
11 ms |
20692 KB |
Output is correct |
| 5 |
Correct |
13 ms |
20588 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
20696 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 3 |
Correct |
11 ms |
20596 KB |
Output is correct |
| 4 |
Correct |
11 ms |
20692 KB |
Output is correct |
| 5 |
Correct |
13 ms |
20588 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
20696 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20692 KB |
Output is correct |
| 2 |
Correct |
14 ms |
20692 KB |
Output is correct |
| 3 |
Correct |
11 ms |
20596 KB |
Output is correct |
| 4 |
Correct |
11 ms |
20692 KB |
Output is correct |
| 5 |
Correct |
13 ms |
20588 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
20696 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
