前提知識

オイラーツアー

解説

https://yukicoder.me/submissions/387104

操作を見ると、妖精がいる頂点数がどんどん減っている。
頂点を削減しながら、順番に見ていく的なことをしていくのかな…
わからんとなったが…

BFS Euler Tour

これは初めて見た。なるほど。
Euler Tourでは通常DFSでやる。
が、BFSでやることである深さについての頂点群が区間に収まる。

区間に帰着させることができたら、あとは区間について総和取得と代入操作ができればいい。
これは遅延評価セグメントツリーにて解決できる。

各クエリについて、以下の要素の総和を取ってくる。

自分
自分の1つ下の子供
自分の2つ下の子供
親
親の1つ下の子
親の親

要素がかぶる場合があるので、消しながら取ってこよう。

int N;
vector<int> E[101010];
LazySegTree<ll, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
int P[101010];
int L1[101010], R1[101010], L2[101010], R2[101010];
int toVID[101010];
void bfs_eulertour()
{
    rep(i, 0, N) {
        P[i] = -1;
        L1[i] = L2[i] = inf;
        R1[i] = R2[i] = -1;
    }

    queue<int> que;
    que.push(0);
    toVID[0] = 0;
    int vid = 1;

    while(!que.empty()) {
        int cu = que.front();
        que.pop();

        fore(to, E[cu]) if(P[cu] != to) {
            que.push(to);
            P[to] = cu;
            toVID[to] = vid;
            vid++;

            int vcu = toVID[cu];

            chmin(L1[vcu], toVID[to]);
            chmax(R1[vcu], toVID[to]);

            if (0 <= P[cu]) {
                int vp = toVID[P[cu]];
                chmin(L2[vp], toVID[to]);
                chmax(R2[vp], toVID[to]);
            }
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    bfs_eulertour();

    rep(i, 0, N) {
        int a;
        cin >> a;
        st.update(toVID[i], toVID[i] + 1, a);
    }

    int Q; cin >> Q;
    rep(q, 0, Q) {
        int x;
        cin >> x;

        int vx = toVID[x];

        ll sm = 0;

        // 自分の1つ下の子供
        if (0 <= L1[vx]) {
            sm += st.get(L1[vx], R1[vx] + 1);
            st.update(L1[vx], R1[vx] + 1, 0);
        }
        // 自分の2つ下の子供
        if (0 <= L2[vx]) {
            sm += st.get(L2[vx], R2[vx] + 1);
            st.update(L2[vx], R2[vx] + 1, 0);
        }
        // 自分
        sm += st.get(vx, vx + 1);
        st.update(vx, vx + 1, 0);
        
        if (0 <= P[x]) {
            int p = P[x];
            int vp = toVID[p];

            // 親
            sm += st.get(vp, vp + 1);
            st.update(vp, vp + 1, 0);

            // 親の1つ下の子
            if (0 <= L1[vp]) {
                sm += st.get(L1[vp], R1[vp] + 1);
                st.update(L1[vp], R1[vp] + 1, 0);
            }

            if (0 <= P[p]) {
                int pp = P[p];
                int vpp = toVID[pp];
                
                // 親の親
                sm += st.get(vpp, vpp + 1);
                st.update(vpp, vpp + 1, 0);
            }
        }

        printf("%lld\n", sm);
        st.update(vx, vx + 1, sm);
    }
}

はまやんはまやんはまやん

hamayanhamayan's blog

γatheree [yukicoder 899]

前提知識

解説