Submission #1364169

#TimeUsernameProblemLanguageResultExecution timeMemory
1364169vlomaczkMigration Plan (JOI25_migration)C++20
100 / 100
3474 ms588736 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define forall(it,x) for(auto& it:(x))
#define mp make_pair
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll M = 2e6 + 10;
ll nxt = 1;
vector<vector<ll>> g(M);
vector<ll> dep(M), pre(M), post(M);

void dfs(ll v) {
	pre[v] = nxt++;
	for(auto u : g[v]) {
		dep[u] = dep[v] + 1;
		dfs(u);
	}
	post[v] = nxt++;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n; cin >> n;
	vector<ll> par(n+1), A(n+1);
	for(ll i=2; i<=n; ++i) {
		cin >> par[i];
		g[par[i]].push_back(i);
	}
	for(ll i=1; i<=n; ++i) cin >> A[i];
	dfs(1);
	vector<multiset<pair<ll, ll>>> D(n+1);
	vector<ll> R(n+1);
	for(ll i=1; i<=n; ++i) R[i] = i; 
	for(ll i=1; i<=n; ++i) {
		D[dep[i]].insert({pre[i], A[i]});
	}
	ll q; cin >> q;
	while(q--) {
		ll t; cin >> t;
		if(t==1) {
			ll a, b;
			cin >> a >> b;
			//merge D[a] -> D[b]

			if(D[R[a]].size() > D[R[b]].size()) {
				swap(R[a], R[b]);
			}
			a=R[a]; b=R[b];
			for(auto x : D[a]) D[b].insert(x);
			while(D[a].size()) D[a].erase(*D[a].begin()); 
		} else if(t==2) {
			ll a, b;
			cin >> a >> b;
			D[R[dep[a]]].insert({pre[a], b});
		} else {
			ll a; cin >> a;
			ll p = R[dep[a]];

			ll res = 0;
			vector<pair<ll, ll>> to_del;
			for(auto it=D[p].lower_bound(mp(pre[a], -1)); it!=D[p].end(); ++it) {
				if(it->first > post[a]) break;
				res += it->second;
				to_del.pb(*it);
			}
			for(auto x : to_del) D[p].erase(x);
			D[p].insert(mp(pre[a], res));
			cout << res << "\n";
		}
	}

	return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...