제출 #855167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855167		mbfibat	Dynamic Diameter (CEOI19_diameter)	C++17	31 / 100	5043 ms	574296 KiB

diameter

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int, int> ii;

const LL INF = 2e18;
const int N = 1e5 + 11;

vector<ii> adj[N];

bool is_c[N];

int totChild = 0;
int nChild[N];
int parCentroid[N];
void cal_child(int u, int p = 0) {
	nChild[u] = 1;
	for (auto [v, w] : adj[u])
		if (!is_c[v] && v != p) {
			cal_child(v, u);
			nChild[u] += nChild[v];
		}	
}
int find_c(int u, int p = 0) {
	for (auto [v, w] : adj[u])
		if (v != p && !is_c[v] && nChild[v] > totChild / 2)
			return find_c(v, u);
	return u;	
}

unordered_map<int, LL> dist;

struct Node {
	LL val = 0, lazy = 0;
	Node* l = nullptr, *r = nullptr;
	Node(){}
};

Node* Seg[N];

void build(Node *cur, int l, int r) {
	if (l == r) {
		cur -> val = dist[l];
		return;
	}
	cur -> l = new Node();
	cur -> r = new Node();
	int mi = (l + r) / 2;
	build(cur -> l, l, mi);
	build(cur -> r, mi + 1, r);
	cur -> val = max(cur -> l -> val, cur -> r -> val);
}

void diffuse(Node *cur, int l, int r) {
	if (cur -> lazy) {
		cur -> val += cur -> lazy;
		if (l != r) {
			cur -> l -> lazy += cur -> lazy;
			cur -> r -> lazy += cur -> lazy;
		}
		cur -> lazy = 0;
	}
}

void upd(Node *cur, int l, int r, int L, int R, LL val) {
	diffuse(cur, l, r);
	if (r < L || R < l) return;
	if (L <= l && r <= R) {
		cur -> lazy += val;
		diffuse(cur, l, r);
		return;
	}

	int mi = (l + r) / 2;
	upd(cur -> l, l, mi, L, R, val);
	upd(cur -> r, mi + 1, r, L, R, val);
	cur -> val = max(cur -> l -> val, cur -> r -> val);
}

LL query(Node *cur, int l, int r, int L, int R) {
	diffuse(cur, l, r);
	if (r < L || R < l) return 0LL;
	if (L <= l && r <= R) return cur -> val;

	int mi = (l + r) / 2;
	LL val_l = query(cur -> l, l, mi, L, R);
	LL val_r = query(cur -> r, mi + 1, r, L, R);
	return max(val_l, val_r);
}

int cur_root;
unordered_map<int, int> top;
map<ii, int> st, ed;

multiset<LL> val_ms[N];
vector<pair<int, LL>> val_ord[N];

void dfs(int u, LL d = 0, int p = 0) {
	st[ii(cur_root, u)] = ++top[cur_root];
	dist[top[cur_root]] = d;

	for (auto [v, w] : adj[u]) {
		if (is_c[v] || v == p) continue;
		dfs(v, d + w, u);
	}
	ed[ii(cur_root, u)] = top[cur_root];
}

LL sol[N];
multiset<LL> ans;

void prep(int root) {
	cur_root = root;

	Seg[root] = new Node();
	dist[root] = 0;
	dfs(root);
	build(Seg[root], 1, top[root]);

	for (auto [v, w] : adj[root]) {
		if (is_c[v]) continue;

		int l = st[ii(root, v)], r = ed[ii(root, v)];
		LL val = query(Seg[root], 1, top[root], l, r);

		val_ms[root].insert(val);
		val_ord[root].emplace_back(l, val);
	}
	sort(val_ord[root].begin(), val_ord[root].end());

	val_ms[root].insert(0); val_ms[root].insert(0);
	val_ord[root].emplace_back(top[root] + 1, 0);

	auto it = val_ms[root].rbegin();
	LL v1 = *it; ++it; LL v2 = *it;
	sol[root] = v1 + v2; ans.insert(sol[root]);
}

void centroid_decompose(int u, int p = 0) {
	cal_child(u); totChild = nChild[u];
	int c = find_c(u);

	parCentroid[c] = p;
	prep(c);

	is_c[c] = true;
	for (auto [v, w] : adj[c])
		if (!is_c[v])
			centroid_decompose(v, c);
}

void upd_edge(int root, int u1, int u2, LL inc) {
	int u = ((st[ii(root, u1)] > st[ii(root, u2)]) ? u1 : u2);
	upd(Seg[root], 1, top[root], st[ii(root, u)], ed[ii(root, u)], inc);

	int p = upper_bound(val_ord[root].begin(), val_ord[root].end(), make_pair(st[ii(root, u)], INF)) - val_ord[root].begin() - 1;
	int l = val_ord[root][p].first, r = val_ord[root][p + 1].first - 1;

	LL old_val = val_ord[root][p].second;
	LL new_val = query(Seg[root], 1, top[root], l, r); 

	val_ms[root].erase(val_ms[root].find(old_val));
	val_ms[root].insert(new_val);
	val_ord[root][p].second = new_val;

	auto it = val_ms[root].rbegin();
	LL v1 = *it; ++it; LL v2 = *it;

	ans.erase(ans.find(sol[root]));
	sol[root] = v1 + v2; ans.insert(sol[root]);

	if (parCentroid[root])
		upd_edge(parCentroid[root], u1, u2, inc);
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, q; LL w; 
	cin >> n >> q >> w;

	vector<LL> W(n);
	vector<ii> edges;
	for (int i = 0; i < n - 1; i++) {
		int u, v; LL c; 
		cin >> u >> v >> c;

		W[i] = c;
		edges.emplace_back(u, v);

		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}
	centroid_decompose(1);

	int last = 0;
	while (q--) {
		int d; LL e; 
		cin >> d >> e;
		d = (d + last) % (n - 1);
		e = (e + last) % w;		

		LL dif = e - W[d]; W[d] = e;

		auto [u, v] = edges[d];
		if (top[u] < top[v]) swap(u, v);

		upd_edge(u, u, v, dif);

		last = *ans.rbegin();
		cout << last << '\n';
	}

}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27