Submission #634793

#	Time	Username	Problem	Language	Result	Execution time	Memory
634793		BackNoob	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	2877 ms	210808 KiB

diameter

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 1e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}


struct IT{
	int n;
	vector<ll> t;
	vector<ll> lz;
	IT(){}
	IT(int _n) {
		n = _n;
		t.resize(n * 4 + 7, 0);
		lz.resize(n * 4 + 7, 0);
	}

	void push_down(int v)
	{
		for(int i = v * 2; i <= v * 2 + 1; i++) {
			t[i] += lz[v];
			lz[i] += lz[v];
		}
		lz[v] = 0;
	}

	void update(int v, int tl, int tr, int l, int r, ll val)
	{
		if(l > r) return;
		if(tl == l && tr == r) {
			t[v] += val;
			lz[v] += val;
		}
		else {
			push_down(v);
			int tm = (tl + tr) / 2;
			update(v * 2, tl, tm, l, min(r, tm), val);
			update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	ll getmax(int v, int tl, int tr, int l, int r)
	{
		if(l > r) return 0;
		if(tl == l && tr == r) return t[v];
		push_down(v);
		int tm = (tl + tr) / 2;
		ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
		ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
		return max(m1, m2);
	}

	void update(int l, int r, ll val)
	{
		update(1, 1, n, l, r, val);
	}
	ll getmax(int l, int r)
	{
		return getmax(1, 1, n, l, r);
	}
} seg[mxN];


struct ITmax{
	int n;
	vector<ll> t;
	ITmax(){}
	ITmax(int _n) {
		n = _n;
		t.resize(n * 4 + 7, 0);
	}

	void update(int v, int tl, int tr, int pos, ll val)
	{
		if(tl == tr) t[v] = val;
		else {
			int tm = (tl + tr) / 2;
			if(pos <= tm) update(v * 2, tl, tm, pos, val);
			else update(v * 2 + 1, tm + 1, tr, pos, val);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	ll getmax(int v, int tl, int tr, int l, int r)
	{
		if(l > r) return 0;
		if(tl == l && tr == r) return t[v];
		int tm = (tl + tr) / 2;
		ll m1 = getmax(v * 2, tl, tm, l, min(r, tm));
		ll m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
		return max(m1, m2);
	}

	void update(int pos, ll val)
	{
		update(1, 1, n, pos, val);
	}
	ll getmax(int l, int r)
	{
		return getmax(1, 1, n, l, r);
	}
} maxval;

struct item{
	int _ll;
	int rr;
	int cc;
};

struct EDGES{
	int u, v;
	ll c;
} eddd[mxN];


int n;
int q;
ll lim;
ll sumnode = 0;
int depth[mxN];
int sub[mxN];
int par[mxN];
bool removed[mxN];
vector<pair<int, ll>> adj[mxN];
vector<int> lef[mxN];
vector<int> rig[mxN];
vector<item> gg[mxN];
multiset<pair<ll, int>> ms[mxN];
int timer = 0;

void dfs_sz(int u, int p)
{
	sub[u] = 1;
	for(auto it : adj[u]) {
		int v = it.fi;
		if(v == p || removed[v] == true) continue;
		dfs_sz(v, u);
		sub[u] += sub[v];
	}
}

int find_centroid(int u, int p, int n)
{
	for(auto it : adj[u]) {
		int v = it.fi;
		if(v == p || removed[v] == true) continue;
		if(sub[v] > n / 2) return find_centroid(v, u, n);
	}
	return u;
}

void dfs(int u, int p, int root, ll cur, int group)
{
	lef[u].pb(++timer);
	seg[root].update(timer, timer, cur);
	for(auto it : adj[u]) {
		int v = it.fi;
		ll c = it.se;
		if(v == p || removed[v] == true) continue;

		if(u == root) dfs(v, u, root, cur + c, v);
		else dfs(v, u, root, cur + c, group);
	}
	rig[u].pb(timer);
}

void dfs_gg(int u, int p, int _ll, int rr, int g)
{
	gg[u].pb({_ll, rr, g});
	for(auto it : adj[u]) {
		int v = it.fi;
		if(v == p || removed[v] == true) continue;
		if(p == -1) dfs_gg(v, u, lef[v].back(), rig[v].back(), v);
		else dfs_gg(v, u, _ll, rr, g);
	}
}

void update_maxval(int p)
{
	ll val = 0;
	if(sz(ms[p]) == 1) {
		pair<ll, int> tmp = *ms[p].begin();
		val = tmp.fi;
	} 	
	if(sz(ms[p]) > 1) {
		auto it = ms[p].end();
		--it;
		pair<ll, int> tmp;
		tmp = *it;
		val += tmp.fi;
		--it;
		tmp = *it;
		val += tmp.fi;
	}

	// cout << p << ' ' << val << endl;
	maxval.update(p, val);
}

void init_centroid(int u, int p)
{
	timer = 0;
	dfs_sz(u, -1);
	int c = find_centroid(u, -1, sub[u]);
	par[c] = p;
	if(p != -1) depth[c] = depth[p] + 1;
	else depth[c] = 0;

	seg[c] = IT(sub[u]);
	dfs(c, -1, c, 0, 0);	

	dfs_gg(c, -1, 0, 0, 0);

	for(auto it : adj[c]) {
		int v = it.fi;
		if(removed[v] == false) {
			int l = lef[v].back();
			int r = rig[v].back();

			ll val = seg[c].getmax(l, r);
			ms[c].insert(make_pair(val, v));
		}
	}


	update_maxval(c);

	removed[c] = true;
	for(auto it : adj[c]) {
		int v = it.fi;
		if(removed[v] == true) continue;;
	 	init_centroid(v, c);
	}
}

void update(int u, int v, ll w)
{
	int x = u;
	int y = v;
	int id1 = 0;
	int id2 = 0;
	while(x != y)
	{
		if(depth[x] > depth[y]) {
			x = par[x];
			++id1;
		}
		else {
			y = par[y];
			++id2;
		}
	}
	while(x != -1) {
		int lu = lef[u][id1];
		int ru = rig[u][id1];
		int lv = lef[v][id2];
		int rv = rig[v][id2];

		if(lu <= lv && rv <= ru) {
			int _ll = gg[v][id2]._ll;
			int rr = gg[v][id2].rr;
			int cc = gg[v][id2].cc;
			ll val = seg[x].getmax(_ll, rr);
			ms[x].erase(ms[x].find(make_pair(val, cc)));
			seg[x].update(lv, rv, w);
			val = seg[x].getmax(_ll, rr);
			ms[x].insert(make_pair(val, cc));

		}
		if(lv <= lu && ru <= rv) {
			int _ll = gg[u][id1]._ll;
			int rr = gg[u][id1].rr;
			int cc = gg[u][id1].cc;
			ll val = seg[x].getmax(_ll, rr);
			ms[x].erase(ms[x].find(make_pair(val, cc)));
			seg[x].update(lu, ru, w);
			val = seg[x].getmax(_ll, rr);
			ms[x].insert(make_pair(val, cc));

		}
		update_maxval(x);
		x = par[x];
		++id1;
		++id2;
	}
}

void solve()
{
	cin >> n >> q >> lim;

	for(int i = 1; i < n; i++) {
		int u, v;
		ll c;
		cin >> u >> v >> c;
		adj[u].pb({v, c});
		adj[v].pb({u, c});
		eddd[i] = {u, v, c};
	}


	maxval = ITmax(n);
	init_centroid(1, -1);	

	for(int i = 1; i <= n; i++) {
		reverse(all(lef[i]));
		reverse(all(rig[i]));
		reverse(all(gg[i]));
	}

	// cout << maxval.getmax(1, n) << endl;
	// return;

	ll last = 0;
	while(q--) {
		ll idx;
		ll w;
		cin >> idx >> w;

		idx = (idx + last) % (n - 1);
		w = (w + last) % lim;	

		// cout << idx << ' ' << w << endl;
		update(eddd[idx + 1].u, eddd[idx + 1].v, w - eddd[idx + 1].c);
		eddd[idx + 1].c = w;
		// update(eddd[idx + 1].u, eddd[idx + 1].v, eddd[idx + 1].c);

		last = maxval.getmax(1, n);
		cout << last << endl;
	}

	// for(int i = 1; i < n; i++) cout << eddd[i].u << ' ' << eddd[i].v << ' ' << eddd[i].c << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("task.inp" , "r" , stdin);
    // freopen(TASK".out" , "w" , stdout);
 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    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