// annoying impl i dont want to deal with rn
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)
#define NN 100010
#define M 1000000007 // 998244353
vector<pl> adj[NN];
ll belong[NN], w[NN]; // maps original edge -> which edge it belongs to now
ll down[NN], par[NN]; // in the new tree, the node below edge I = down[i], and parent of node X in new tree
ll parEdge[NN]; // wehn traversing par, what is the edge I use
ll curw[NN]; // current weight of edge
ll edgeidx = 0;
void dfs(ll i, ll p, ll vpar) {
ll children = 0;
for (auto [x, _]: adj[i]) if (x-p) children++;
if (children == 1) {
for (auto [x, eidx]: adj[i]) if (x-p) {
belong[eidx] = edgeidx;
dfs(x, i, vpar);
}
} else {
if (i != 1) {
down[edgeidx] = i;
par[i] = vpar;
parEdge[i] = edgeidx;
edgeidx++;
}
for (auto [x, eidx]: adj[i]) if (x-p) {
belong[eidx] = edgeidx;
dfs(x, i, i);
}
}
}
multiset<ll> all_answer; // all subtree answers
ll curans[NN]; //current answer
multiset<ll> childrenPull[NN]; // the curD's of my children
map<ll, ll> children[NN]; // children -> curD
ll ROOT(ll i) {
return par[i] == i || par[i] == -1;
}
void multiset_erase(multiset<ll>& a, ll value){
assert(a.find(value) != a.end());
a.erase(a.find(value));
}
ll getOneEdge(ll i) { // CANNOT be 1
assert(childrenPull[i].size() != 1);
if (childrenPull[i].size() == 0) return 0;
return *childrenPull[i].rbegin();
}
void recompute(ll i, ll modified) {
// cout << "asking to recompute " << i << " with child " << modified << " modified " << endl;
// cout << "lol " << i << " " << modified << endl;
// recomptues maximal down
// cout << "LOL " << childrenPull[i].size() << ": ";
// for (auto x: childrenPull[i]) cout << x << " , "; cout << endl;
assert(children[i].count(modified));
multiset_erase(childrenPull[i], children[i][modified]);
children[i][modified] = curw[parEdge[modified]] + getOneEdge(modified);
childrenPull[i].insert(children[i][modified]);
// cout << "OK: recomputed. My things are: \n";
// for (const auto [k, v]: children[i]) cout << k << ": " << v << endl;
// cout << "children pull: ";
// for (const auto x: childrenPull[i]) cout << x << " "; cout << endl;
// cout << parEdge[modified] << ":WTF " << curw[parEdge[modified]] << endl;
assert(children[i].size() == childrenPull[i].size());
// cout << "Yo " << endl;
// recomputes answer
multiset_erase(all_answer, curans[i]);
if (childrenPull[i].size() <= 1)
curans[i] = getOneEdge(i);
else {
// cout << "wtf " << endl;
auto v = childrenPull[i].rbegin();
ll t = *v;
v = ++childrenPull[i].rbegin();
t += *v;
// cout << "AFTER " << t << endl;
curans[i] = t;
}
// cout << "Ya " << endl;
all_answer.insert(curans[i]);
if (!ROOT(i)) recompute(par[i], i);
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
G(n) G(q) G(W)
memset(par, -1, sizeof par);
vector<ll> weights(n-1);
vector<pl> shits;
F(i, 0, n-1) {
G(x) G(y) cin >> weights[i];
adj[x].emplace_back(y, i);
adj[y].emplace_back(x, i);
shits.emplace_back(x, y);
}
// We want to dfs from a non-leaf root node.
// Unless n=2; then it's trivial.
if (n==2) {
ll last = 0;
while (q--) {
G(d) G(e)
d = (d + last)%(n-1);
e = (e + last)%W;
last = e;
cout << last << '\n';
}
exit(0);
}
F(root, 1, n+1) if (adj[root].size() >1) {
dfs(root, -1, root); break;
}
F(i, 1, n+1) if (~par[i]) {
if (!ROOT(i)) {
children[par[i]][i] = 0;
childrenPull[par[i]].insert(0);
}
all_answer.insert(curans[i] = 0);
// cout << "Alive: " << i << endl;
}
// F(i, 0, n-1) cout << i << " -> " << belong[i] << endl;
auto upd = [&](ll i, ll we) {
ll cur = belong[i];
curw[cur] -= w[i];
w[i] = we;
curw[cur] += w[i];
// cout << "just updated, thought new cur " << cur << " is " << curw[cur] << endl;
// cout << "wee wee " << i << " " << we << endl;
// cout << "THIS BELONGS TO " << belong[i] << endl;
// cout << "BELONG I SPANS " << down[cur] << "TO " << par[down[cur]] << endl;
assert(par[down[cur]] != down[cur]);
recompute(par[down[cur]], down[cur]);
};
F(i, 0, n-1) upd(i, weights[i]);
ll last = 0;
// cout << "current: " << endl;
// F(k, 1, n+1) cout << k << ": " << curans[k] << endl;
while (q--) {
G(d) G(e)
d = (d + last)%(n-1);
e = (e + last)%W;
// cout << "Modifying " << d << " to " << e << endl;
// if (q == 0){
// F(i, 0, n-1) {
// cout << shits[i].K << " " << shits[i].V << " " << w[i] << endl;
// }
// F(j, 0, edgeidx) {
// cout << "FAKE EDGE " << j << " FROM " << down[j] << " to " << par[down[j]] << ": " << curw[j] << endl;
// }
// }
upd(d, e);
// cout << "current: " << endl;
// F(k, 1, n+1) cout << k << ": " << curans[k] << endl;
last = *all_answer.rbegin();
cout << last << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
17496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
17496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
17496 KB |
Output is correct |
| 2 |
Correct |
5 ms |
17500 KB |
Output is correct |
| 3 |
Correct |
4 ms |
17476 KB |
Output is correct |
| 4 |
Correct |
12 ms |
17760 KB |
Output is correct |
| 5 |
Correct |
43 ms |
18000 KB |
Output is correct |
| 6 |
Correct |
4 ms |
17496 KB |
Output is correct |
| 7 |
Correct |
5 ms |
17756 KB |
Output is correct |
| 8 |
Correct |
4 ms |
17756 KB |
Output is correct |
| 9 |
Correct |
5 ms |
17756 KB |
Output is correct |
| 10 |
Correct |
16 ms |
18032 KB |
Output is correct |
| 11 |
Correct |
62 ms |
18984 KB |
Output is correct |
| 12 |
Correct |
9 ms |
18780 KB |
Output is correct |
| 13 |
Correct |
9 ms |
18780 KB |
Output is correct |
| 14 |
Correct |
11 ms |
19032 KB |
Output is correct |
| 15 |
Correct |
30 ms |
19340 KB |
Output is correct |
| 16 |
Correct |
100 ms |
20308 KB |
Output is correct |
| 17 |
Correct |
180 ms |
41400 KB |
Output is correct |
| 18 |
Correct |
183 ms |
41392 KB |
Output is correct |
| 19 |
Correct |
197 ms |
41568 KB |
Output is correct |
| 20 |
Correct |
220 ms |
41908 KB |
Output is correct |
| 21 |
Correct |
465 ms |
43220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
17752 KB |
Output is correct |
| 2 |
Correct |
18 ms |
17756 KB |
Output is correct |
| 3 |
Correct |
68 ms |
18064 KB |
Output is correct |
| 4 |
Correct |
128 ms |
18256 KB |
Output is correct |
| 5 |
Correct |
40 ms |
19924 KB |
Output is correct |
| 6 |
Correct |
63 ms |
19928 KB |
Output is correct |
| 7 |
Correct |
140 ms |
20228 KB |
Output is correct |
| 8 |
Correct |
269 ms |
20684 KB |
Output is correct |
| 9 |
Correct |
256 ms |
29388 KB |
Output is correct |
| 10 |
Correct |
286 ms |
29424 KB |
Output is correct |
| 11 |
Correct |
404 ms |
29684 KB |
Output is correct |
| 12 |
Correct |
556 ms |
30444 KB |
Output is correct |
| 13 |
Correct |
620 ms |
41164 KB |
Output is correct |
| 14 |
Correct |
628 ms |
41148 KB |
Output is correct |
| 15 |
Correct |
778 ms |
41668 KB |
Output is correct |
| 16 |
Correct |
957 ms |
41944 KB |
Output is correct |
| 17 |
Correct |
1309 ms |
41668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
72388 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
17496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
