<center> <h1> week of 11/14 </h1>

usaco pt 2
</center>

---
### `📝 notes`

ill be participating in [calico](https://calico.berkeley.edu) this weekend!

---

## misc.

### [Rorororobot](https://codeforces.cc/contest/1709/problem/D)
---

#### `problem:`
you are given an $n \times m$ grid, with the last $s_i$ blocks of column $i$ blocked off.

next, you are given $q$ queries.

* you are given $(x,y), (x1,y1), k$
* the robot starts at $(x, y)$ and can freely move around the grid in all $4$ directions. if the robot ever hits a blocked off cell or goes outside the grid, it explodes.
* the robot is broken, and every instruction you give it, the robot repeats it $k$ times.

figure out whether it's possible to travel between the two cells.

#### `solution`

firstly, we know that we have to travel a distance of exactly $|c-c1|$, so this value must be divisible by $k$.

next, we also have to make sure that it's even possible to get to the other side, taking the blocked cells into account.

let's try the largest possible value, $\lfloor (n-r)/k \rfloor \cdot k + r$. if this is less than or equal to the largest value between $c$ and $c-1$, this won't work. we'll query the maximum value between the two with a segment tree.

if this row value $- r1$ is divisible by $k$, we're done!

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

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#ifdef LOCAL
#define endl "\n"
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif
#define int ll

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}
template <class T>
struct Seg {	// comb(ID,b) = b
	const T ID = -1e18;
	T comb(T a, T b) { return max(a, b); }
	int n;
	vector<T> seg;
	void init(int _n) {
		n = _n;
		seg.assign(2 * n, ID);
	}
	void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }
	void upd(int p, T val) {	// set val at position p
		seg[p += n] = val;
		for (p /= 2; p; p /= 2) pull(p);
	}
	T query(int l, int r) {	 // max on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
			if (l & 1) ra = comb(ra, seg[l++]);
			if (r & 1) rb = comb(seg[--r], rb);
		}
		return comb(ra, rb);
	}
};
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	Seg<ll> tree;
	tree.init(m);

	for (int i = 0; i < m; i++) {
		ll x;
		cin >> x;
		tree.upd(i, x);
	}

	int q;
	cin >> q;

	for (int i = 0; i < q; i++) {
		int r, c, r1, c1, k;
		cin >> r >> c >> r1 >> c1 >> k;

		if (c == c1) {
			if (abs(r - r1) % k) {
				cout << "NO" << endl;
			} else {
				cout << "YES" << endl;
			}
			continue;
		}

		bool ok = 1;

		if (abs(c1 - c) % k) ok = 0;
		ll h = ((n - r) / k) * k;
		h += r;
		if (abs(h - r1) % k) ok = 0;

		ll mx = tree.query(min(c - 1, c1 - 1), max(c - 1, c1 - 1));
		// cout << mx << endl;
		if (h <= mx) ok = 0;
		cout << (ok ? "YES" : "NO") << endl;
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

### [Paths on the Tree](https://codeforces.cc/contest/1746/problem/D)
---

#### `problem:`
i don't think the problem statement is that confusing, so here ya go.

* basically any two nodes which share the same parent should not have the number of paths differ by more than $1$.
* the score is the number of paths that go through the node $\times s_i$, where $s_i$ is the score array which is given to you.

find the max score.

#### `solution:`

the number of paths which go throuhg the first layer of nodes (nodes which share the parent $1$) should be $\lfloor \frac{n}{\texttt{nadj}} \rfloor$, and $n \mod \texttt{nadj}$ nodes should have $\lfloor \frac{n}{\texttt{nadj}} \rfloor + 1$.

we'll greedily choose the best nodes with a DFS.

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#ifdef LOCAL
// #define endl "\n"
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif
#define int ll
#define endl "\n"

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		int n, k;
		cin >> n >> k;

		vector<vector<int>> adj(n);
		for (int i = 1; i < n; i++) {
			int x;
			cin >> x;
			--x;
			adj[x].push_back(i);
		}
		vector<int> score(n);
		for (int i = 0; i < n; i++) {
			cin >> score[i];
		}

		// each part of adj[0] naturally gets  k / sz(adj[0]), and we'll add remainders greedily
		map<int, int> dp;
		const int ct = 1e9 + 7;

		function<int(int u, int rem)> dfs = [&](int u, int rem) {
			int key = u * ct + rem;
			if (dp.count(key)) return dp[key];
			int gain = 0;
			if (sz(adj[u])) {
				int split = rem / sz(adj[u]);
				int ext = rem % sz(adj[u]);

				vector<int> could;

				for (int i = 0; i < sz(adj[u]); i++) {
					int prev = dfs(adj[u][i], split);
					gain += prev;
					if (ext) could.push_back(dfs(adj[u][i], split + 1) - prev);
				}
				if (ext) sort(all(could));
				while (ext) {
					gain += could.back();
					could.pop_back();
					ext--;
				}
				// dbg(split);
			}

			return dp[key] = gain + (score[u] * rem);
		};

		ll ans = dfs(0, k);
		cout << ans << endl;

#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

## what's a segment tree?

a segment tree essentially lets you do point update and range query in $\mathcal{O}(n \log n)$ for **any associative** operation.

so... that means, we can update any point in an our segment tree (or essentially an index) in $\mathcal{O}(\log n)$, slower than a standard array.

BUT, we can query a range in $\log n$, instead of $n$.

this works because we use a "divide-and-conquer" approach when aswering these queries. $f(n) = f(0,\frac{n}{2}) + (\text{operation}) + f(\frac{n}{2} + 1, n)$.

for example, let's say we want to use the associative operation of addition on the array:

$$\{1, 2, -2, -1\}$$


from this, we know that the number of nodes will stay linear, because $2^{\lceil \log_2n\rceil} < 4n$

when we query a contiguous subarray of this tree, we'll keep searching down the tree until we reach the targeted end points. the time complexity is $\log n$ because only the most left and right pointers can extend. In the worst case, they both "spawn" two new pointers, so at most, we visit $4$ nodes at each level. this makes the time complexity for a query $4 \log n$


Thus, we can query any *associative* operation in $\mathcal{O}(\log n)$ with $\mathcal{O}(\log n)$ point updates.