Submission #594589

#	Time	Username	Problem	Language	Result	Execution time	Memory
594589		penguinhacker	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	410 ms	47820 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, q, eu[mxN], ev[mxN], tin[mxN], tout[mxN];
ll wlim, ew[mxN], lz[1<<19];
vector<int> adj[mxN];
vector<ll> stk;

void dfs(int u=0, int p=-1, ll d=0) {
	tin[u]=stk.size();
	stk.push_back(d);
	for (int e : adj[u]) {
		int v=eu[e]^ev[e]^u;
		if (v!=p) {
			dfs(v, u, d+ew[e]);
			stk.push_back(d);
		}
	}
	tout[u]=stk.size()-1;
}

struct Node {
	ll ans, mn, mx, lhs, rhs;
} st[1<<19];

Node cmb(Node a, Node b) {
	return {
		max({a.ans, b.ans, a.rhs+b.mx, a.mx+b.lhs}),
		min(a.mn, b.mn),
		max(a.mx, b.mx),
		max({a.lhs, b.lhs, -2*a.mn+b.mx}),
		max({a.rhs, b.rhs, a.mx-2*b.mn})
	};
}

void bld(int u=1, int l=0, int r=2*n-2) {
	if (l==r) {
		st[u].mn=st[u].mx=stk[l];
		st[u].lhs=st[u].rhs=-stk[l];
		return;
	}
	int mid=(l+r)/2;
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

void psh(int u, int l, int r) {
	if (lz[u]) {
		st[u].mn+=lz[u], st[u].mx+=lz[u], st[u].lhs-=lz[u], st[u].rhs-=lz[u];
		if (l!=r)
			lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
		lz[u]=0;
	}
}

void upd(int ql, int qr, ll x, int u=1, int l=0, int r=2*n-2) {
	psh(u, l, r);
	if (l>qr||r<ql)
		return;
	if (ql<=l&&r<=qr) {
		lz[u]+=x;
		psh(u, l, r);
		return;
	}
	int mid=(l+r)/2;
	upd(ql, qr, x, 2*u, l, mid);
	upd(ql, qr, x, 2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> wlim;
	for (int i=0; i<n-1; ++i) {
		cin >> eu[i] >> ev[i] >> ew[i], --eu[i], --ev[i];
		adj[eu[i]].push_back(i);
		adj[ev[i]].push_back(i);
	}
	dfs();
	bld();
	ll ans=0;
	while(q--) {
		int i;
		ll nxt;
		cin >> i >> nxt;
		i=(i+ans)%(n-1);
		nxt=(nxt+ans)%wlim;
		int u=tin[eu[i]]<tin[ev[i]]?ev[i]:eu[i];
		upd(tin[u], tout[u], nxt-ew[i]);
		ew[i]=nxt;
		cout << (ans=st[1].ans) << "\n";
	}
	return 0;
}

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