제출 #1341986

#제출 시각아이디문제언어결과실행 시간메모리
1341986SpyrosAlivMigration Plan (JOI25_migration)C++20
0 / 100
2003 ms228684 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MN = 2e6+5;
const int MQ = 2e6+5;
const int MX = 4e6+11;
const int LOG = 25;

vector<vector<int>> act(MN), tree(MN);
bool isAct[MN];
int cnt[MN], dep[MN], par[MN], lastNode[MX], root[MX], repDep[MX];
int up[MN][LOG];
int n, q;
int curr = 0;

void get_depths(int node) {
    up[node][0] = par[node];
    for (int i = 1; i < LOG; i++) {
        up[node][i] = up[up[node][i-1]][i-1];
    }
    act[dep[node]].push_back(node);
    isAct[node] = true;
    for (auto next: tree[node]) {
        dep[next] = dep[node] + 1;
        get_depths(next);
    }
}

int get_anc(int u, int k) {
    for (int i = 0; i < LOG; i++) {
        if ((k >> i) & 1) {
            u = up[u][i];
        }
    }
    return u;
}

void solve() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> par[i];
        tree[par[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> cnt[i];
    }
    get_depths(1);
    for (int i = 0; i < n; i++) {
        root[i] = curr;
        lastNode[i] = curr;
        repDep[i] = i;
        curr++;
    }
    cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y;
            root[lastNode[x]] = root[lastNode[y]];
            lastNode[x] = curr;
            root[curr] = curr;
            repDep[curr] = x;
            curr++;
        }
        else if (t == 2) {
            assert(false);
        }
        else if (t == 3) {
            int u; cin >> u;
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                int currDep = dep[i];
                int rr = root[currDep];
                int lastDep = repDep[rr];
                int needUp = currDep - lastDep;
                int fin = get_anc(i, needUp);
                if (fin == u) ans += cnt[i];
            }
            cout << ans << "\n";
        }
    }
}

signed main() {
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...