hi i'm back with another solution thing

whatever you like to call it

this time it's this problem from the codeforces educational portal or whatever

pretty standard dsu problem, except this time you need to

- get the value of a certain node
- increment all the values of a set (given by a certain node) by some value

and there's the standard linking operation but that's obvious lmao

so at first i thought about storing points in a `points` array and then just
incrementing the root of each set when the input asked me to increment a set

then when they queried for the amt of points
i could just sum up the `points` array for each node that was on the path
from the current node to the root and win basically

but then i realized if the root already had some previous value when it was declared as the parent of another set, this would also cause the set that was merged into the parent to be incremented by what was already in the root

take the sample input for example- we have `points[1]` to be `100`, but then when we merge node `3` into node `1`, now the algorithm thinks that node `3` also has `100` points, even though it was just node `1`

so we fix this by keeping an array `extra_points` that stores the initial value in the root and then subtract the values in the array when querying to tell all the points that were previously there when merged to screw off

also disclaimer path compression isn't used because it would mess up the algorithm

think it's still possible tho

since no one reads this i'll just say i wanna be a femboy

```cpp #include <iostream> #include <vector> #include <string> #include <algorithm> using std::cout; using std::endl; using std::vector; class Players { private: vector<int> parents; vector<int> sizes; vector<int> points; vector<int> extra_points; public: Players(int size) : parents(size), sizes(size, 1), points(size), extra_points(size) { for (int i = 0; i < size; i++) { parents[i] = i; } } int get_ultimate(int n) { return parents[n] == n ? n : get_ultimate(parents[n]); } int get_points(int n) { int amt = points[n]; if (parents[n] == n) { return amt; } amt += get_points(parents[n]) - extra_points[n]; return amt; } void add_points(int n, int p) { int top = get_ultimate(n); points[top] += p; } bool link(int n1, int n2) { n1 = get_ultimate(n1); n2 = get_ultimate(n2); if (n1 == n2) { return false; } if (sizes[n1] < sizes[n2]) { std::swap(n1, n2); } sizes[n1] += sizes[n2]; parents[n2] = n1; extra_points[n2] = points[n1]; return true; } }; /** * https://codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/problem/C * 3 6 * add 1 100 * join 1 3 * add 1 50 * get 1 * get 2 * get 3 should output 150, 0, and 50, each on a new line */ int main() { int node_num; int query_num; std::cin >> node_num >> query_num; Players players(node_num + 1); for (int q = 0; q < query_num; q++) { std::string type; std::cin >> type; if (type == "get") { int n; std::cin >> n; cout << players.get_points(n) << endl; } else if (type == "add") { int n; int points; std::cin >> n >> points; players.add_points(n, points); } else if (type == "join") { int a; int b; std::cin >> a >> b; players.link(a, b); } } } ```