KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) C - 山登り(Mountain Climbing)

データ構造の良い練習。

問題:C: 山登り(Mountain Climbing) - KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) | AtCoder

解法:各頂点ごとに,その頂点がグラフの葉であるなら山の頂点(頂点0)までの距離を格納しておき,セグメント木を使ってそれらの最小値を求める,という形で各クエリを処理していく。
具体的には,まず最初に木のグラフから各葉の頂点0までの距離を求める(ソースコードではinit()の部分)。そして,各クエリである辺が消されたら,グラフは木であるので子供側の頂点から下側の頂点は,すべて頂点0に到達することができなくなる。よって,次のように処理すれば良い(ソースコードではerase(v, p)の部分。vが注目している頂点で,pがvの親)。
・vがすでに処理済み(頂点0に到達できないとわかっている頂点)ならそのままreturnする。
・そうでないなら,その下にある頂点をすべて到達不能であるというフラグを立てていく。vが葉であるなら,頂点0への距離をINFに更新する。

各頂点に到達するのは合計でO(N)となり,またセグメント木で各クエリごとに最小値を求めるのにかかる計算量はO(log N)なので計算量的に間に合う。
以下ソースコード

struct edge {
    int to;
    int cost;
    edge() {}
    edge(int t, int c) : to(t), cost(c) {}
};

const int MAXN = 100100;
const int INF = 1e9;
vector<edge> G[MAXN];
int P[MAXN];
bool vis[MAXN];

// segment tree
int seg[4*MAXN];
int n;

void nodeInit(int, int, int);

void init(int N) {
    n = 1;
    while (n < N) n <<= 1;
    // とりまINFに初期化
    for (int i = 0; i < 2*n-1; i++) seg[i] = INF;
    // 木を辿って行って適当にsegのノードを変えていく
    nodeInit(0, -1, 0);
}

void change(int k, int x) {
    k += n-1;
    seg[k] = x;
    while (k) {
        k = (k-1)/2;
        seg[k] = min(seg[k*2+1], seg[k*2+2]);
    }
}

int query(int a, int b, int k, int l, int r) {
    if (b <= l || a >= r) return INF;
    if (a <= l && r <= b) return seg[k];
    return min(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r));
}

int query(int a, int b) {
    return query(a, b, 0, 0, n);
}

void nodeInit(int v, int p, int dist) {
    bool leaf = true;
    for (auto e : G[v]) {
        if (e.to == p) continue;
        leaf = false;
        nodeInit(e.to, v, dist+e.cost);
    }
    if (leaf) change(v, dist);
}

void erase(int v, int p) {
    if (vis[v]) return;
    vis[v] = true;
    bool leaf = true;
    for (auto e : G[v]) {
        if (e.to == p) continue;
        leaf = false;
        erase(e.to, v);
    }
    if (leaf) {
        change(v, INF);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    for (int i = 1; i < N; i++) {
        int w;
        cin >> P[i] >> w;
        P[i]--;
        G[i].push_back(edge(P[i], w));
        G[P[i]].push_back(edge(i, w));
    }
    init(N);
    while (Q--) {
        int x;
        cin >> x;
        x--;
        erase(x, P[x]);
        int ans = query(0, n);
        if (ans >= INF) ans = -1;
        cout << ans << endl;
    }
    return 0;
}