Algoogle

Algorithm for Programming Contest

Codeforces 418D Big Problems for Organizers

Category: Codeforces Tag: data-structure, doubling, lowest-common-ancestor, tree

Big Problems for Organizers

問題概要


頂点数n(<=100000)の木が与えられる. この時m回以下のクエリが与えられる.
頂点u, vから最も遠い点との距離はいくらか. ただし距離はu, vからのそれぞれの距離のうち小さい方を使う.

解法


便宜上適当な頂点を根としておく.
2頂点の中間部分で木を分解すれば, その木の根をそれぞれu, vとすることで木の高さが最長距離に当たる.

クエリのu, vは深さの降順になっているとする.
w = LCA(u,v)とすると, 分割点cはdepth[u] = depth[v]ならw, そうでないならuとwの間にある.

そうするとuを含む方の木は以下の場合分けで高さが求まる.

  • 元の木でuの子孫に最も遠い点がある
  • uとcの間にuから最も遠い点がある

部分木の高さは各点の深さと一緒に計算すればよい(O(n)).
ここでuとcの間というのは, uの祖先だけでなく, 祖先の子孫も含む(ただしu以下は含まない).
これはdoublingで2の冪個先の祖先までの区間について求めておけばO(log n)で求まる(構築はO(n log n)).
これでuを含む方の木については調べられた.

v(とw)を含む木の方は, 以下の場合分けで求まる

  • vの子孫に最も遠い点がある
  • vとwの間にvまでの最も遠い点がある
  • wと根の間にvまでの最も遠い点がある
  • vとcの間にvまでの最も遠い点がある
  • その他のwの子孫(子供が根になる部分木にv, cを含まない)に最も遠い点がある

始めの3つはuの時と同じdoublingで求めてあるやつを使えば良い.
4つ目は今までのと似ているが, 基準の点が祖先の方なので別に用意する(似たようなdoublingをするだけ).
最後は各頂点に対してその頂点を根とする部分木の高さを求めるとき, その子を根とする部分木の高さが最も大きい3つを保存すれば良い.
そのとき子供の番号も保存しておけば, その頂点がvまたはcの祖先にいるかで使うかどうかを決めることができる.

以上をバグらないように実装する.

コード


(418D.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
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#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)
#define pb push_back
typedef pair<int,int> pii;
const int M1 = 100010, M2 = 32;

int N, M, E;
vector<int> G[M1];
inline void add_edge(int u, int v){ G[u].pb(v); G[v].pb(u);}
inline void chmax(int &a, int b){a=max(a,b);}
int par[M1][M2], depth[M1], up[M1][M2], down[M1][M2];
pii max3[M1][3];

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

void build_max3(int v, int u, int d){
    depth[v] = d;
    for(int &w: G[v]) if(w != u){
        build_max3(w,v,d+1);
        if(max3[w][0].first+1 > max3[v][2].first){
            max3[v][2].first = max3[w][0].first+1;
            max3[v][2].second = w;
            sort(max3[v], max3[v]+3);
            reverse(max3[v], max3[v]+3);
        }
    }
}

void build_updown(int v, int u){
    par[v][0] = u;
    rep(i,3){
        if(max3[u][i].second == v) continue;
        up[v][0] = max3[u][i].first+1;
        down[v][0] = max3[u][i].first+1;
        break;
    }
    rep(i,E) if(par[v][i] != -1){
        par[v][i+1] = par[par[v][i]][i];
        if(par[v][i+1] < 0) break;
        up[v][i+1] = max(up[v][i], up[par[v][i]][i]+(1<<i));
        down[v][i+1] = max(down[par[v][i]][i], down[v][i]+(1<<i));
    }
    for(int &w: G[v]) if(w != u) build_updown(w,v);
}

void build(){
    E = 0;
    while((1<<E) < N) E++;
    memset(par,-1,sizeof(par));
    build_max3(0,-1,0);
    for(int &w: G[0]) build_updown(w,0);
}

int get_center(int u, int d){
    d = (d-1)/2;
    for(int i = E; i >= 0; i--)
        if(d&(1<<i)) u = par[u][i];
    return u;
}

int get_umax(int v, int d){
    int cnt = 0, ret = 0;
    if(d<0) return -1e9;
    rep(i,E) if(d&(1<<i)){
        chmax(ret, up[v][i]+cnt);
        cnt |= 1<<i;
        v = par[v][i];
    }
    return ret;
}

int get_dmax(int v, int d){
    int ret = 0;
    if(d<0) return -1e9;
    rep(i,E) if(d&(1<<i)){
        d ^= 1<<i;
        chmax(ret, down[v][i]+d);
        v = par[v][i];
    }
    return ret;
}

int query(int u, int v){
    if(depth[u] < depth[v]) swap(u,v);
    int w = lca(u,v), ans = max3[u][0].first;
    int d = depth[u]+depth[v]-2*depth[w];
    int vwd = depth[v]-depth[w], c = get_center(u,d);
    chmax(ans, get_umax(v, vwd-1));
    chmax(ans, get_umax(u, (d-1)/2));
    chmax(ans, get_umax(w, depth[w])+vwd);
    chmax(ans, get_dmax(c, depth[c]-depth[w]-1)+vwd);
    if(w != v) chmax(ans, max3[v][0].first);
    rep(i,3){
        int a = lca(max3[w][i].second, u), b = lca(max3[w][i].second, v);
        if(a == max3[w][i].second or b == max3[w][i].second) continue;
        chmax(ans, max3[w][i].first+vwd);
        break;
    }
    return ans;
}

void solve(){
    build();
    while(M--){
        int u, v; scanf("%d%d", &u, &v);
        printf("%d\n", query(u-1,v-1));
    }
}

void input(){
    scanf("%d", &N);
    rep(i,N-1){
        int u, v; scanf("%d%d", &u, &v);
        add_edge(u-1,v-1);
    }
    scanf("%d", &M);
}

int main(){
    input();
    solve();
    return 0;
}

Comments