Submission #624420

#	Time	Username	Problem	Language	Result	Execution time	Memory
624420		iomoon191	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	630 ms	70408 KiB

meetings2

#include <bits/stdc++.h>
using ll = long long;
#define int ll
using namespace std;

#define sz(x) (int)(x).size()
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define mod 998244353

#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;

const ll N = 200005;
const ll inf = 1e18;

int n, dep[N], par[25][N], sz[N],mz[N], res[N];
vi adj[N], v[N];

void dfs(int u, int p){
	sz[u] = 1;
	mz[u] = 0;
	for(auto &i : adj[u]){
		if(i == p) continue;
		par[0][i] = u;
		dep[i] = dep[u] + 1;
		dfs(i, u);
		sz[u] += sz[i];
		mz[u] = max(mz[u], sz[i]);
	}
}

int center(){
	dfs(1, 0);
	pi res(inf, -inf);
	foru(i, 1, n){
		int ryz = max(n - sz[i], mz[i]);
		res = min(res, pi(ryz, i));
	}
	return res.se;
}

int lca(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	int dif = dep[y] - dep[x];
	for(int i = 0; dif; i++, dif >>= 1){
		if(dif & 1) y = par[i][y];
	}
	if(x == y) return x;
	ford(i, 16, 0){
		if(par[i][x] != par[i][y]){
			x = par[i][x];
			y = par[i][y];
		}
	}
	return par[0][x];
}

int dis(int x, int y){
	return dep[x] - dep[lca(x, y)] + dep[y] - dep[lca(x, y)];
}

void solve(){
	cin >> n;
	foru(i, 1, n - 1){
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int cen = center();
	dfs(cen, -1);
	foru(i, 1, 20){
		foru(j, 1, n){
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	foru(i, 1, n){
		if(i == cen) continue;
		v[sz[i]].push_back(i);
	}
	pi cur(cen, cen);
	ford(i, n >> 1, 0){
		for(auto &i : v[i]){
			int f = cur.fi;
			int s = cur.se;
			cur = max(cur, pi(f, i), [&](pi a, pi b){
				return dis(a.fi, a.se) < dis(b.fi, b.se);
			});
			cur = max(cur, pi(s, i), [&](pi a, pi b){
				return dis(a.fi, a.se) < dis(b.fi, b.se);
			});
		}
		res[i << 1] = dis(cur.fi, cur.se);
	}
	foru(i, 1, n) cout << res[i] + 1 << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1; // cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80