2020/2021 COCI Contest #1

작성일 | In

Overview

3시간 5문제 셋입니다. 앞쪽 2문제는 난이도순, 나머지 3문제는 난이도 상관 없이 섞어놓은 것 같습니다.

체감 난이도는 1 < 2 < 4 < 5 < 3 순입니다.
2번 문제는 KOI 고등부 1번, 3번 문제는 KOI 고등부 4번, 4번 문제는 KOI 중등부 3번, 5번 문제는 KOI 중등부 3번 정도의 난이도인 것 같습니다.
코드는 글 하단에 한 번에 올리겠습니다.

문제 지문 : https://hsin.hr/coci/contest1_tasks.pdf

Task 1. Patkice (50점)

문제

N by M 격자가 주어지고, o에서 출발해 x로 가려고 합니다.
처음 이동방향은 마음대로 정할 수 있고, 그 다음부터는 < > ^ v에 따라 이동 방향이 결정 됩니다. x로 도달할 수 있는지 판별하는 문제입니다.

풀이

단순 구현 문제입니다.

Task 2. Bajka (70점)

문제

길이가 300 이하인 두 문자열 S와 T가 주어집니다. (두 문자열의 길이는 서로 다를 수 있습니다.)

S의 임의의 위치에서 시작해 적절히 이동을 해서, 최소 거리만큼 이동해 T를 만드는 것이 목표입니다. 3가지 방법으로 이동할 수 있습니다.

  1. 왼쪽으로 한 칸 이동하고 그 칸에 있는 문자를 T에 추가한다. 이때 이동 거리는 1이다.
  2. 오른쪽으로 한 칸 이동하고 그 칸에 있는 문자를 T에 추가한다. 이때 이동 거리는 1이다.
  3. 현재 칸과 동일한 문자가 적혀있는 칸으로 이동한다. x에서 y로 이동한다고 하면 이동 거리는 $\vert x - y \vert$ 이다.

문자열을 만들 수 있는 경우에는 최소 거리를 출력하고, 그렇지 않은 경우에는 -1을 출력하는 문제입니다.

풀이

D(i, j) = T의 i번째 글자까지 완성했고, 현재 S의 j번째 위치에 있을 때 최소 이동 거리
로 DP를 정의하면 O(N^2M)에 문제를 풀 수 있습니다.

Task 3. 3D Histogram (110점)

문제

3차원 히스토그램에서 가장 부피가 큰 직육면체의 부피를 구하는 문제입니다.

N ≤ 2000인 경우를 해결하면 20점을 받을 수 있고, N ≤ 2e5인 경우를 해결하면 90점을 추가로 받을 수 있습니다.

풀이

2차원의 경우는 매우 유명한 문제이고, 모노톤 스택을 이용한 풀이와 분할 정복을 이용한 풀이가 있습니다. 모노톤 스택을 이용하는 것은 어려울 것 같으니 분할 정복 풀이를 생각해봅시다.

구간 [st, ed]에 대해 중점 md를 지나는 경우를 모두 처리한 뒤, 구간 [st, md-1]과 [md+1, ed]에 대해 재귀적으로 처리할 것입니다.

두 함수 f(i, j)와 g(i, j)를 아래와 같이 정의합시다.
$f(i, j) = \min_{i \leq k \leq j} (a_k), \ g(i, j) = \min_{i \leq k \leq j} (b_k)$

f(st, ed) * g(st, ed) * (ed - st + 1)을 최대화 하는 것이 이 문제의 목표입니다.

구간의 양 끝점 st, ed와 중간 지점 md에 대해, 4가지 경우로 분류할 수 있습니다.

  1. f(st, md) ≤ f(md, ed) && g(st, md) ≤ g(md, ed)
  2. f(st, md) ≤ f(md, ed) && g(st, md) ≥ g(md, ed)
  3. f(st, md) ≥ f(md, ed) && g(st, md) ≥ g(md, ed)
  4. f(st, md) ≥ f(md, ed) && g(st, md) ≤ g(md, ed)

1, 2만 처리하면 적절히 뒤집고 swap하는 것으로 3, 4번을 똑같이 처리할 수 있습니다. 1, 2에 대한 풀이를 알아봅시다.

1번 케이스는 투포인터로 O(ed - st + 1)만에 쉽게 해결할 수 있습니다.
각 시작점 s에 대해, f(s, e) = f(s, m)이고 g(s, e) = g(s, m)인 e의 최댓값을 찾아서 최대 부피를 갱신해주면 됩니다. (아래 코드에서 calc1 함수를 참고하세요.)

2번 케이스는 복잡합니다.
f(s, m) * g(m, e) * (e - s + 1)을 최대화 하는 것이 목적입니다.
식을 좀 변형하면, f(s, m) * (-s + 1) * g(m, e) + f(s, m) * e * g(m, e)가 됩니다.
f(s, m)으로 묶어주면, f(s, m) * { g(m, e) * (-s + 1) + e * g(m, e) }가 됩니다.

중괄호 안쪽의 식은 g(m, e)를 기울기, e*g(m, e)를 y절편으로 하는 일차함수라고 생각할 수 있습니다. 일차함수의 최댓값을 구하는 것은 Convex Hull Trick을 이용해 빠르게 구할 수 있으니, 이 성질을 이용해서 풀이를 찾아봅시다.

먼저 1번 케이스처럼 각 시작점 s에 대해, f(s, e) = f(s, m)이고 g(s, e) = g(s, m)이 되도록 하는 e의 구간을 각각 전처리해줍시다. O(ed - st + 1) 시간에 가능합니다. 이 구간을 l(s), r(s)라고 합시다.

각 시작점 s에 대해, l(s)부터 r(s)번째 직선들 중에서 (-l + 1) 시점에서의 최댓값을 구하면 됩니다. 이는 세그먼트 트리의 각 정점에서 CHT를 관리하는 것으로 처리할 수 있습니다.

세그먼트 트리의 각 정점에 저장되는 직선의 기울기와 쿼리로 주어지는 x 좌표인 (-l + 1) 모두 단조성이 있으니 CHT를 선형에 처리할 수 있습니다.

$T(N) = 2T(N/2) + O(N \log N)$이므로 $O(N \log^2 N)$에 문제를 풀 수 있습니다.

Task 4. Papričice (110점)

문제

트리가 주어집니다. 트리의 간선을 2개 제거하면 3개의 컴포넌트로 나누어질텐데, 가장 큰 컴포넌트와 가장 작은 컴포넌트의 차이를 최소화하는 것이 이 문제의 목표입니다.

N ≤ 200인 경우를 해결하면 15점, N ≤ 2000인 경우를 해결하면 35점, N ≤ 2e5인 경우를 해결하면 60점을 받아 총 110점 만점입니다.

풀이

풀이 설명과 구현의 편의를 위해 임의의 정점을 루트로 잡아서 rooted tree로 만듭시다.
제거하는 두 간선의 양 끝에 달린 정점 중 깊이 있는 정점을 각각 x, y라고 합시다.
(1) x, y가 조상 관계인 경우와 (2) 그렇지 않은 경우, 2가지로 나누어서 생각합시다.

1번 케이스를 먼저 봅시다. 일반성을 잃지 않고, x가 y의 조상이라고 합시다. 각 컴포넌트의 크기는 S[y], S[x] - S[y], N - S[x]가 됩니다.
2번 케이스에서 각 컴포넌트의 크기는 S[x], S[y], N - S[x] - S[y]가 됩니다.

각 y에 대해서 적절한 x를 찾아 세 컴포넌트의 크기가 최대한 같아지도록 만들면 됩니다.
1번 케이스는 S[x]가 (N+S[y])/2에 가까워야하고, 2번 케이스는 S[x]가 (N-S[y])/2에 가까워야합니다.
DFS를 돌면서, std::set에 lower_bound를 적당히 사용해주면 $O(N \log N)$만에 정답을 구할 수 있습니다.

“정답이 D 이하일 것이다.” 라고 파라메트릭 서치를 하면서 Persistent Segment Tree를 쓰면 $O(N \log^2 N)$, Merge Sort Tree를 쓰면 $O(N \log^3 N)$인데, 두 풀이 모두 TLE가 납니다. 개인적으로는 N ≤ 50000인 서브태스크가 있었으면 더 좋았을 것 같습니다.
이 코드도 아래에 같이 올리겠습니다.

Task 5. Tenis (110점)

문제

N명의 선수가 풀리그 방식으로 테니스 경기를 합니다. 테니스 코트는 3가지 종류가 있고, 각 코트마다 참가자들의 순위가 주어집니다. 두 선수가 어떤 코트에서 경기를 한다면, 그 코트에서 순위가 높은 선수가 무조건 이깁니다.

우리는 코트마다 참가자들의 순위가 주어졌을 때, 각 경기를 적절한 코트에서 진행해 최대한 좋은 경기가 되도록 만드려고 합니다.
좋은 경기라는 것은, 경기의 승자가 가장 잘하는 코트에서 진행되는 경기를 의미합니다. (예를 들어 A 코트에서 경기를 했을 때 승자는 A 코트에서의 순위가 2등이고, B 코트에서 경기를 했을 때 승자는 B 코트에서의 순위가 1등이라면 B 코트에서 경기를 진행하는 것이 더 좋은 경기입니다.)
어떤 두 코트에서 승자의 순위가 똑같다면, 패자의 순위가 더 높은 것이 좋은 경기입니다. 승자와 패자 모두 순위가 같다면 더 작은 번호의 코트에서 진행하면 됩니다.

N(N-1)/2번의 경기를 최대한 좋은 경기로 진행했을 때, 각 코트가 사용된 횟수와 각 선수가 이긴 횟수를 출력하면 됩니다.

N ≤ 3000인 경우 50점을 받고, N ≤ 1e5인 경우 60점을 받습니다.

풀이

문제를 이해하는 것이 가장 어렵습니다.

각 경기를 (1) 어떤 선수의 최대 순위가 다른 선수의 최대 순위보다 높은 경우와 (2) 그렇지 않은 경우, 총 2가지로 분류할 수 있습니다. 또한 2번 케이스는 최대 3N번 밖에 일어나지 않습니다. (두 선수 모두 최대 순위가 i인 경우는 최대 3가지 밖에 없습니다.)

2번 케이스는 간단하게 처리할 수 있으니 1번 케이스만 설명하겠습니다. 2번 케이스에 대한 처리 방법이 궁금하면 아래 코드에서 go 함수를 참고하세요.

1번 케이스를 해결하는 방법을 알아봅시다.
기본적인 접근 방법은, 각 사람에 대해 그 사람보다 잘하는 사람의 수(그 사람이 지는 경우의 수)를 구하는 것입니다.

각 사람의 순위가 제일 높아지는 경기장을 비트로 표현합시다. 3비트로 표현되고, 공집합은 없기 때문에 7가지가 나옵니다. 순위가 제일 높은 경기장이 bit인 사람들의 최고 등수를 정렬해서 배열 vec[bit]에 저장합시다.
vec[bit]에서 i번째 사람보다 잘하는 사람의 수는 이진탐색(std::lower_bound)를 이용해 쉽게 구할 수 있습니다. 어떤 코트에서 경기를 진행해야할지 결정만 하면 됩니다.

승자는 비트가 켜져있는 코트에서 모두 동일한 퍼포먼스가 나오기 때문에 패자의 순위만 최소화하면 됩니다. 이것은 비트마스크를 이용해 간단하게 구현할 수 있습니다.

정답 코드

Task 1
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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, m, si, sj; char a[111][111];
int mn = 1e9; char res;
int chk[111][111];

void go(int i, int j, char c){
    memset(chk, 0, sizeof chk);
    int cnt = 0;
    while(1){
        cnt++;
        if(chk[i][j]++) return;
        if(a[i][j] == '.') return;
        if(a[i][j] == 'x') break;
        if(a[i][j] == '>') j++;
        else if(a[i][j] == '<') j--;
        else if(a[i][j] == '^') i--;
        else if(a[i][j] == 'v') i++;
    }
    if(mn > cnt) mn = cnt, res = c;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        cin >> a[i][j];
        if(a[i][j] == 'o') si = i, sj = j;
    }
    go(si, sj+1, 'E');
    go(si-1, sj, 'N');
    go(si+1, sj, 'S');
    go(si, sj-1, 'W');
    if(mn == 1e9) cout << ":(";
    else cout << ":)\n" << res;
}
Task 2
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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, m;
char a[333], b[333];
ll dp[333][333];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=m; i++) cin >> b[i];
    memset(dp, 0x3f, sizeof dp);

    for(int i=1; i<=n; i++) if(a[i] == b[1]) dp[1][i] = 0;
    for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) if(b[i] == a[j]) {
        if(j > 1) dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
        if(j < n) dp[i][j] = min(dp[i][j], dp[i-1][j+1] + 1);
        for(int k=1; k<=n; k++) if(a[k] == b[i-1]) {
            if(a[k] == a[j-1]) dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(j-1-k) + 1);
            if(a[k] == a[j+1]) dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(j+1-k) + 1);
        }
    }
    ll mn = 1e18;
    for(int i=1; i<=n; i++) mn = min(mn, dp[m][i]);
    if(mn > 1e17) cout << -1;
    else cout << mn;
}
Task 3
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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

ll ccw(const p &a, const p &b, const p &c){
    ll dx1 = b.x - a.x, dy1 = b.y - a.y;
    ll dx2 = c.x - b.x, dy2 = c.y - b.y;
    return dx1*dy2 - dx2*dy1;
}

ll n, a[202020], b[202020], mx;
vector<p> tree[1 << 19];
p val[202020]; int pv[1 << 19];
void build(int node, int s, int e){
    tree[node].clear();
    if(s == e){
        tree[node].push_back(val[s]);
        pv[node] = 0;
        return;
    }
    int m = s + e >> 1;
    build(node << 1, s, m);
    build(node << 1 | 1, m+1, e);
    vector<p> &hull = tree[node];
    hull = tree[node << 1];
    for(auto i : tree[node << 1 | 1]){
        while(hull.size() >= 2 && ccw(hull[hull.size()-2], hull.back(), i) <= 0) hull.pop_back();
        hull.push_back(i);
    }
    pv[node] = hull.size() - 1;
}
inline ll f(int node, int idx, ll x){ return tree[node][idx].x * x + tree[node][idx].y; }
ll query(int node, ll x){
    while(pv[node]-1 >= 0 && f(node, pv[node], x) <= f(node, pv[node]-1, x)) pv[node]--;
    return f(node, pv[node], x);
}
ll query(int node, int s, int e, int l, int r, ll x){
    if(r < s || e < l) return 0;
    if(l <= s && e <= r) return query(node, x);
    int m = s + e >> 1;
    return max(query(node << 1, s, m, l, r, x), query(node << 1 | 1, m+1, e, l, r, x));
}

void calc1(int st, int md, int ed){
    ll a_mn = a[md], b_mn = b[md];
    int pv = md;
    for(int i=md; i>=st; i--){
        a_mn = min(a_mn, a[i]);
        b_mn = min(b_mn, b[i]);
        while(pv+1 <= ed && a_mn <= a[pv+1] && b_mn <= b[pv+1]) pv++;
        mx = max(mx, a_mn * b_mn * (pv - i + 1));
    }
}

p range[202020];
void calc2(int st, int md, int ed){
    ll a_mn = a[md], b_mn = b[md];
    int s = md, e = md;
    for(int i=md; i>=st; i--){
        a_mn = min(a_mn, a[i]);
        b_mn = min(b_mn, b[i]);
        while(e < ed && a_mn <= a[e+1]) e++;
        while(s <= ed && b_mn < b[s]) s++;
        range[i] = p(s, e);
    }
    b_mn = b[md];
    for(int i=md; i<=ed; i++){
        b_mn = min(b_mn, b[i]);
        val[i] = p(b_mn, i * b_mn);
    }
    build(1, md, ed);
    a_mn = a[md];
    for(int i=md; i>=st; i--){
        a_mn = min(a_mn, a[i]);
        ll t = a_mn * query(1, md, ed, range[i].x, range[i].y, -i+1);
        mx = max(mx, t);
    }
}

void dnc(int st, int ed){
    if(st > ed) return;
    if(st == ed){ mx = max(mx, a[st] * b[st]); return; }
    int md = st + ed >> 1;
    calc1(st, md, ed);
    calc2(st, md, ed);
    dnc(st, md-1);
    dnc(md+1, ed);
}

void rev(){ reverse(a+1, a+n+1); reverse(b+1, b+n+1); }
void swp(){ for(int i=1; i<=n; i++) swap(a[i], b[i]); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i] >> b[i];
    dnc(1, n); swp(); dnc(1, n);
    rev();
    dnc(1, n); swp(); dnc(1, n);
    cout << mx;
}
Task 4
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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, sz[202020], mn = 1e9+7;
vector<int> g[202020];
multiset<int> in, out;

int dfs(int v, int b = -1){
    sz[v] = 1;
     for(auto i : g[v]) if(i != b) sz[v] += dfs(i, v);
    return sz[v];
}

inline void f(int a, int b, int c){
    int t = max({a, b, c}) - min({a, b, c});
    mn = min(mn, t);
}

void solve(int v, int b = -1){
    auto it1 = in.lower_bound((n+sz[v])/2);
    if(it1 != in.end()) f(sz[v], *it1-sz[v], n-*it1);
    if(it1 != in.begin()) --it1, f(sz[v], *it1-sz[v], n-*it1);
    auto it2 = out.lower_bound((n-sz[v])/2);
    if(it2 != out.end()) f(sz[v], *it2, n-sz[v]-*it2);
    if(it2 != out.begin()) --it2, f(sz[v], *it2, n-sz[v]-*it2);

    in.insert(sz[v]);
    for(auto i : g[v]) if(i != b) solve(i, v);
    in.erase(in.find(sz[v]));
    out.insert(sz[v]);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<n; i++){
        int s, e; cin >> s >> e;
        g[s].push_back(e); g[e].push_back(s);
    }
    dfs(1, -1);
    solve(1, -1);
    cout << mn;
}
Task 5
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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int n, a[3][101010], rnk[3][101010], mn[101010];
vector<int> vec[8];
ll cnt[3], lose[101010];
set<p> st;

void go(int x, int y){
    if(x > y) swap(x, y);
    if(x == y || st.count(p(x, y))) return;
    st.emplace(x, y);

    p t[3]; int flag[3] = {0};
    for(int k=0; k<3; k++){
        t[k] = p(a[k][x], a[k][y]);
        if(t[k].x > t[k].y) swap(t[k].x, t[k].y), flag[k] = 1;
    }
    int idx = min_element(t, t+3) - t;
    cnt[idx]++; (flag[idx] ? lose[x] : lose[y])++; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=0; i<3; i++) for(int j=1; j<=n; j++) cin >> rnk[i][j], a[i][rnk[i][j]] = j;
    for(int i=1; i<=n; i++){
        mn[i] = min({ a[0][i], a[1][i], a[2][i] });
        int bit = 0;
        for(int j=0; j<3; j++) if(a[j][i] == mn[i]) bit |= (1 << j);
        vec[bit].push_back(mn[i]);
    }
    for(int i=0; i<8; i++) sort(all(vec[i]));

    for(int i=1; i<=n; i++){
        for(int j=0; j<3; j++) for(int k=j+1; k<3; k++) {
            int x = rnk[j][i], y = rnk[k][i];
            if(mn[x] == i && mn[y] == i) go(x, y);
        }
    }
    for(int i=1; i<=n; i++){
        for(int bit=0; bit<8; bit++){
            int val = IDX(vec[bit], mn[i]), court = -1;
            for(int j=0; j<3; j++) if(bit & (1 << j)) {
                if(court == -1 || a[j][i] < a[court][i]) court = j;
            }
            cnt[court] += val; lose[i] += val;
        }
    }

    for(int i=0; i<3; i++) cout << cnt[i] << " "; cout << "\n";
    for(int i=1; i<=n; i++) cout << n-1-lose[i] << " ";
}

부분 점수 코드

Task 4 - O(N log^3 N) with Merge Sort Tree
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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
const int S = 1 << 18;

int n, in[202020], out[202020], sz[202020], pv;
vector<int> g[202020];
int dfs(int v, int b = -1){
    sz[v] = 1; in[v] = ++pv;
    for(auto i : g[v]) if(i != b) sz[v] += dfs(i, v);
    out[v] = pv;
    return sz[v];
}

vector<int> tree[1 << 19];
void build(){
    for(int i=1; i<=n; i++) tree[in[i]|S].push_back(sz[i]);
    for(int i=S-1; i; i--) merge(all(tree[i << 1]), all(tree[i << 1 | 1]), back_inserter(tree[i]));
}
int query(int l, int r, int t1, int t2){
    if(t1 > t2) return 0;
    l |= S; r |= S; vector<int> ret;
    while(l <= r){
        if(l & 1){
            int t = upper_bound(all(tree[l]), t2) - lower_bound(all(tree[l]), t1);
            if(t > 0) return 1; l++;
        }
        if(~r & 1){
            int t = upper_bound(all(tree[r]), t2) - lower_bound(all(tree[r]), t1);
            if(t > 0) return 1; r--;
        }
        l >>= 1; r >>= 1;
    }
    return 0;
}

int chk(int d){
    for(int i=1; i<=n; i++){
        int x = sz[i], l, r;
        l = max({x-d, n-d-2*x, (n-x-d+1)/2});
        r = min({x+d, n+d-2*x, (n-x+d)/2});
        if(out[i]+1 <= n && query(out[i]+1, n, l, r)) return 1;

        l = max({(x-d+1)/2, n-x-d, 2*x-n-d});
        r = min({(x+d)/2, n-x+d, 2*x-n+d});
        if(in[i]+1 <= out[i]-1 && query(in[i]+1, out[i]-1, l, r)) return 1;
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<n; i++){
        int s, e; cin >> s >> e;
        g[s].push_back(e); g[e].push_back(s);
    }
    dfs(1); build();

    int l = 0, r = n;
    while(l < r){
        int m = l + r >> 1;
        if(chk(m)) r = m;
        else l = m + 1;
    }
    cout << r;
}
Task 4 - O(N log^2 N) with Persistent Segment Tree
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
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

const int S = 1 << 18;

int n, in[202020], out[202020], sz[202020], pv;
vector<int> g[202020];
int dfs(int v, int b = -1){
    sz[v] = 1; in[v] = ++pv;
    for(auto i : g[v]) if(i != b) sz[v] += dfs(i, v);
    out[v] = pv;
    return sz[v];
}

struct Node{
    int l, r, v;
    Node(){ l = r = v = 0; }
};

struct PST{
    int n, pv, root[202020];
    Node nd[5050505];
    PST(int n) : n(n) { memset(root, 0, sizeof root); }
    void init(int node, int s, int e){
        if(s == e) return;
        int m = s + e >> 1;
        if(!nd[node].l) nd[node].l = pv++;
        if(!nd[node].r) nd[node].r = pv++;
        init(nd[node].l, s, m); init(nd[node].r, m+1, e);
    }
    void init(){
        pv = 1;
        for(int i=0; i<=n; i++) root[i] = pv++;
        init(root[0], 1, n);
    }
    void update(int prv, int now, int s, int e, int x){
        if(s == e){ nd[now].v = nd[prv].v + 1; return; }
        int m = s + e >> 1;
        if(x <= m){
            if(!nd[now].l) nd[now].l = pv++;
            nd[now].r = nd[prv].r;
            update(nd[prv].l, nd[now].l, s, m, x);
        }
        else{
            if(!nd[now].r) nd[now].r = pv++;
            nd[now].l = nd[prv].l;
            update(nd[prv].r, nd[now].r, m+1, e, x);
        }
        nd[now].v = nd[nd[now].l].v + nd[nd[now].r].v;
    }
    int query(int now, int s, int e, int l, int r){
        if(r < s || e < l) return 0;
        if(l <= s && e <= r) return nd[now].v;
        int m = s + e >> 1;
        return query(nd[now].l, s, m, l, r) + query(nd[now].r, m+1, e, l, r);
    }
};

void build(PST &tree){
    vector<int> v(n); iota(all(v), 1);
    sort(all(v), [&](int a, int b){ return in[a] < in[b]; });
    for(int i=1; i<=n; i++) tree.update(tree.root[i-1], tree.root[i], 1, n, sz[v[i-1]]);
}
int query(PST &tree, int l, int r, int t1, int t2){
    if(l > r || t1 > t2) return 0;
    int X = tree.query(tree.root[r], 1, n, t1, t2);
    int Y = tree.query(tree.root[l-1], 1, n, t1, t2);
    return X-Y > 0;
}

int chk(PST &tree, int d){
    for(int i=1; i<=n; i++){
        int x = sz[i], l, r;
        l = max({x-d, n-d-2*x, (n-x-d+1)/2});
        r = min({x+d, n+d-2*x, (n-x+d)/2});
        if(out[i]+1 <= n && query(tree, out[i]+1, n, l, r)) return 1;

        l = max({(x-d+1)/2, n-x-d, 2*x-n-d});
        r = min({(x+d)/2, n-x+d, 2*x-n+d});
        if(in[i]+1 <= out[i]-1 && query(tree, in[i]+1, out[i]-1, l, r)) return 1;
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; PST pst(n); pst.init();
    for(int i=1; i<n; i++){
        int s, e; cin >> s >> e;
        g[s].push_back(e); g[e].push_back(s);
    }
    dfs(1); build(pst);

    int l = 0, r = n;
    while(l < r){
        int m = l + r >> 1;
        if(chk(pst, m)) r = m;
        else l = m + 1;
    }
    cout << r;
}