#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
#endif
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
template <class T>
istream &operator>>(istream &in, vector<T> &a)
{
for (T &x : a)
in >> x;
return in;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &a)
{
for (T x : a)
out << x << " ";
out << "\n";
return out;
}
struct SegTree
{
pair<int, int> get(int l, int r)
{
return get(0, n, 0, l, r);
}
void inc(int l, int r, int x)
{
inc(0, n, 0, l, r, x);
}
SegTree(const vector<int> &a)
{
n = a.size();
updates = vector<int>(4 * n);
b = vector<pair<int, int>>(4 * n);
build(0, n, 0, a);
}
SegTree() {}
private:
int n = 0;
vector<pair<int, int>> b = {};
vector<int> updates = {};
void push(int l, int r, int i)
{
if (l + 1 == r)
return;
updates[i * 2 + 1] += updates[i];
updates[i * 2 + 2] += updates[i];
b[i * 2 + 1].first += updates[i];
b[i * 2 + 2].first += updates[i];
updates[i] = 0;
}
pair<int, int> build(int l, int r, int i, const vector<int> &a)
{
if (l + 1 == r)
return b[i] = pair<int, int>{a[l], l};
int m = (l + r) / 2;
return b[i] = max(build(l, m, i * 2 + 1, a), build(m, r, i * 2 + 2, a));
}
pair<int, int> get(int l, int r, int i, int ql, int qr)
{
if (l >= qr || r <= ql)
return {LLONG_MIN / 2, -1};
if (l >= ql && r <= qr)
return b[i];
push(l, r, i);
int m = (l + r) / 2;
return max(get(l, m, i * 2 + 1, ql, qr), get(m, r, i * 2 + 2, ql, qr));
}
pair<int, int> inc(int l, int r, int i, int ul, int ur, int x)
{
if (l >= ur || r <= ul)
return b[i];
if (l >= ul && r <= ur)
{
updates[i] += x;
b[i].first += x;
return b[i];
}
push(l, r, i);
int m = (l + r) / 2;
return b[i] = max(inc(l, m, i * 2 + 1, ul, ur, x), inc(m, r, i * 2 + 2, ul, ur, x));
}
};
struct Tree
{
int n;
unordered_map<int, vector<pair<int, int>>> edges;
unordered_map<int, int> pre;
unordered_map<int, int> subtree;
unordered_map<int, int> initial_parent;
vector<int> pre_order;
vector<int> pre_dist;
int timer = 0;
int centroid = -1;
SegTree pre_dist_seg;
int find_centroid(int i, int p = -1)
{
int subtree_size = 1;
int largest_subtree = 0;
for (auto [c, D] : edges[i])
{
if (c != p)
{
int sub = find_centroid(c, i);
subtree_size += sub;
largest_subtree = max(largest_subtree, sub);
}
}
if (largest_subtree <= n / 2 && n - subtree_size <= n / 2)
centroid = i;
return subtree_size;
}
void get_edges(int i, int p, unordered_map<int, vector<pair<int, int>>> &out)
{
for (auto [c, d] : edges[i])
{
if (c == centroid)
continue;
out[i].push_back({c, d});
if (c != p)
get_edges(c, i, out);
}
}
int dfs(int i, int d = 0, int p = -1)
{
pre[i] = timer++;
pre_order.push_back(i);
pre_dist[pre[i]] = d;
int subtree_size = 1;
if (p == -1)
initial_parent[i] = -1;
else if (initial_parent[p] == -1)
initial_parent[i] = i;
else
initial_parent[i] = initial_parent[p];
for (auto [c, D] : edges[i])
{
if (c != p)
{
subtree_size += dfs(c, d + D, i);
}
}
subtree[i] = subtree_size;
return subtree_size;
}
vector<unordered_map<int, vector<pair<int, int>>>> split()
{
vector<unordered_map<int, vector<pair<int, int>>>> out;
for (auto [c, d] : edges[centroid])
{
unordered_map<int, vector<pair<int, int>>> subset;
get_edges(c, centroid, subset);
out.push_back(move(subset));
}
return out;
}
Tree(unordered_map<int, vector<pair<int, int>>> edges) : edges{edges}
{
n = edges.size();
pre_dist = vector<int>(n);
int start;
for (auto [i, c] : edges)
{
start = i;
break;
}
find_centroid(start);
assert(centroid != -1);
dfs(centroid);
pre_dist_seg = SegTree(pre_dist);
}
int update(int a, int b, int c)
{
if (subtree.count(a) != 0 && subtree.count(b) != 0)
{
if (pre[a] > pre[b])
swap(a, b);
int dist_lower = pre_dist_seg.get(pre[b], pre[b] + 1).first;
int dist_upper = pre_dist_seg.get(pre[a], pre[a] + 1).first;
int old_weight = dist_lower - dist_upper;
int delta = c - old_weight;
pre_dist_seg.inc(pre[b], pre[b] + subtree[b], delta);
}
auto [dist, i] = pre_dist_seg.get(0, n);
int bad_child = initial_parent[pre_order[i]];
auto dist2 = pre_dist_seg.get(0, pre[bad_child]).first;
auto dist3 = pre_dist_seg.get(pre[bad_child] + subtree[bad_child], n).first;
return dist + max({dist2, dist3, 0l});
}
};
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, q, w;
cin >> n >> q >> w;
unordered_map<int, vector<pair<int, int>>> edges;
vector<pair<int, int>> aint_edges;
for (int i = 0; i < n - 1; i++)
{
int a, b;
int c;
cin >> a >> b >> c;
a--, b--;
edges[a].push_back({b, c});
edges[b].push_back({a, c});
aint_edges.push_back({a, b});
}
vector<Tree> subtrees;
subtrees.push_back(Tree(edges));
queue<int> todo;
todo.push(0);
vector<vector<int>> trees_using(n, {0});
while (todo.size())
{
int index = todo.front();
todo.pop();
auto out = subtrees[index].split();
for (auto &x : out)
{
if (x.size() > 1)
{
int new_index = subtrees.size();
todo.push(new_index);
subtrees.push_back(Tree(x));
for (auto [i, c] : x)
{
if (trees_using[i].back() != new_index)
trees_using[i].push_back(new_index);
}
}
}
}
vector<int> subtree_result(subtrees.size());
set<pair<int, int>> results;
for (int i = 0; i < subtrees.size(); i++)
{
subtree_result[i] = subtrees[i].update(-1, -1, -1);
results.insert({subtree_result[i], i});
}
int last = 0;
while (q--)
{
int d, e;
cin >> d >> e;
d = (d + last) % int(n - 1);
e = (e + last) % w;
auto [a, b] = aint_edges[d];
int out = 0;
for (int i : trees_using[a])
{
results.erase({subtree_result[i], i});
subtree_result[i] = subtrees[i].update(a, b, e);
results.insert({subtree_result[i], i});
}
out = prev(results.end())->first;
cout << out << "\n";
last = out;
}
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from diameter.cpp:7:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
diameter.cpp: In function 'int main()':
diameter.cpp:300:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<Tree>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
300 | for (int i = 0; i < subtrees.size(); i++)
| ~~^~~~~~~~~~~~~~~~~
