Algoogle

Algorithm for Programming Contest

Codeforces 379F New Year Tree

Category: Codeforces Tag: lowest-common-ancestor, tree

New Year Tree

問題概要


はじめに根1とその3つの子2~4がある.
q(<=5e5)回の以下のクエリを捌け.

  • 頂点vに2つの頂点を加え, 木の直径を答える

解法


木の直径は一番離れた2点の距離.
初期では頂点2, 3の距離が当てはまる.
頂点を追加するたびにその頂点と, 現在の直径で使われている2点の距離をみる.
もし距離が大きくなるなら頂点を交換する.
距離はLCAを求めればよいのでO(log n)で計算可能.

コード


(379F.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)

int q, n;
int par[1<<20][32], dep[1<<20];

void add(int v){
    par[n][0] = par[n+1][0] = v;
    dep[n] = dep[n+1] = dep[v]+1;
    rep(i,20) par[n][i+1] = par[n+1][i+1] = par[par[n][i]][i];
}

int lca(int u, int v){
    if(dep[u] > dep[v]) swap(u,v);
    int dif = dep[v] - dep[u];
    rep(i,21) if(dif&(1<<i)) v = par[v][i];
    if(u == v) return u;
    for(int i = 20; i >= 0; i--)
        if(par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    return par[u][0];
}

int dist(int u, int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}

void solve(){
    int u = 2, v = 3, d = 2, x;
    dep[2] = dep[3] = dep[4] = 1;
    par[2][0] = par[3][0] = par[4][0] = 1;
    n = 5;
    while(q--){
        scanf("%d", &x);
        add(x);
        int du = dist(n,u), dv = dist(n,v);
        if(du > d) v = n, d = du;
        else if(dv > d) u = n, d = dv;
        n += 2;
        printf("%d\n", d);
    }
}

int main(){
    scanf("%d", &q);
    solve();
    return 0;
}

Comments