Apparently my posts are "repetitive", "not good quality", and "useless" so i guess ill try to make a good one.
My teacher told me that instead of learning how to do different problems in different creative ways (sounds yuck in general), be lazy and use the same way, and he taught me how to peel leaves off the tree.
So if you go to a tree and start peeling the leaves, you'll prob never finish off the tree. One reason is because there's too much leaves and the second reason is because the entire tree isn't made of leaves so you'll be left with branches when you're done. The first problem is easily solved cus we're using a computer algorithm and not actually peeling leaves. The second one is trickier though, how would you delete a tree by only peeling leaves. It's actually a lot simpler than it seems. You just have to use the secret technique to turn branches of a tree into leaves so u can peel them off too.
I know this just sounds like I'm spouting nonsense (apparently like my other posts) but I'm actually not. Look at an actual computer science tree.
If you don't know what a leaf is, it's a node that is only connected to one other node in an undirected tree, or a node that has no children. I double bordered all the leaves in the image. So now our beautiful beautiful tree has a stump and branches growing out from the stump, finally reaching the double bordered leaves at the end. Now we can pluck off these leaves. Fun right, I love plucking leaves of trees while going outside. Anyways after you pluck off all the trees you get this new tree (with all the edges from the plucked leaves removed).
Now you might be wondering, what are the new double bordered nodes? Well they are nodes with 0 children, or only connected to one other node. "WAIT A SECOND, THATS A LEAF!" — probably you as soon as you see this part of the beautiful post. You're right smart one, after you pluck off the leaves (very soothing task by the way you should try it sometime) you get more leaves. Unlike in real life where you get actual branches. Yuck! Now you might be thinking, I can keep peeling the leaves, and to that I say good job thats pretty much it. Here are the pictures of the tree as you keep peeling.
Good job! You have successfully learned how to delete a tree (hopefully). Now you're probably thinking why is this useful? Well it isn't... IF you aren't doing anything and just mindlessly (or should I say algorithmlessly) plucking off leaves.
For example, let's look into how to use this technique for an actual USACO silver tree problem (the entire goal of the post).
This problem is classified as greedy on USACO guide, and everyone hates when they can't figure out a simple greedy idea. Since this problem is a tree problem, think about how to peel the leaves. You know that every single node has to have one infect at the end of the days. Thinking about this and leaves gives us the question, how does a leaf get a infect?
Simple, leaves can only get an infect from their parent. This means that a parent has to double enough times to give 1 infect to every single one of its children. Why is this true? Think about this, if a parent has 1 node, and its parent has how much ever it could possibly need. The parent needs to provide for the children as we said earlier. This is only done if the parent has enough infects to give to each one of its children, and keep one for itself (all nodes need to have an infect including the parent). This leads to the observation that node i needs to have child[i]+1 infects. To get this amount, it could either get 1 and then continue to double, or get child[i]+1, separate 1s from the parent. obviously, getting one and doubling is faster or the same as getting each one from the parents in all scenarios, because it is an exponential vs a linear (1 : 1, 2 : 2, 4 : 3, 8 : 4, ... exponential mogs). This means that we can get the idea that a parent of x children should get 1 infect from its parent, and then double until it has >= x+1 infects.
That's the greedy idea for the problem; double the infects until it's enough for its children and yourself. For the full solution, loop through each node, find how much doubles it takes, and how much moves it takes to move to the children, and add it all up for all nodes.
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
// notice how the adjacency list isn't even needed or even any graph algorithm
// number of connections to node i
vector<int> con(n, 0);
for (int i = 0; i < n-1; i++){
int a, b; cin >> a >> b; a--; b--;
con[a]++;
con[b]++;
}
int ans = 0;
for (int i = 1; i < n; i++){
// find how much times the infects need to double
int infects = 1;
// it should be number of children + 1, which is the same as
// con[i]-1 (subtract parent) + 1 and the ones cancel
while (infects < con[i]){
infects *= 2; ans++;
}
// add the number of moves to the children
ans += con[i]-1;
}
// finally add the answer for the root node
int infects = 1;
// root doesn't have a parent so its con[0]+1 (the one isn't subtracted)
while (infects < con[0]+1){
infects *= 2; ans++;
}
// add children
ans += con[0];
cout << ans << endl;
}
Here is the code if you need it. Notice how I don't actually use leaf peeling in the code, but instead only use it to get the greedy idea. The point of leaf peeling is that it makes the problem a lot simpler to view.
Let's look at a harder example (squarey).
The point of the problem is to move haybales from barn to barn so that all the barns have an equal amount of haybales.
Look straight at the leaves. The first thing you notice is that the leaves are only connected to one other barn, meaning that it can only move haybales too/take haybales from one barn. This means that if a leaf has too much bales (more than the average), it has to pass it's bales on too the neighbor. If otherwise, it has to take from the neighbor. Thats pretty much the idea, except after taking/giving, the node is removed, parent is updated, and a new leaf can be formed. This follows the leaf peeling process and gives our answer on which barns to move bales from. Now the only issue is what order should these movements be printed in. This part is pretty intuitive, if a barn is giving, it means it is giving enough so it can be equal to average. This will only increase the parent and decrease the current node down to the average, so no values will be negative. This allows the process to be printed very first. The second type of process is where the parent gives to the child. If the parent gives to the child, the parent could be in the negative, causing its parent to give to it. This could cause a chain of being negatives starting from the root node. To avoid the negatives, reverse the order in which the bales are given from the parents to the children, so that the process starts at the root node, and is never negative.
Thats it! leaf peeling for the win.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define int long long
struct ans{
int startbarn;
int endbarn;
int baleamt;
};
signed main(){
int n; cin >> n;
vector<int> bales(n);
int avg = 0;
for (int i = 0; i < n; i++){
cin >> bales[i];
avg += bales[i];
}
avg = avg/n;
vector<vector<int>> adj(n);
vector<int> con(n, 0);
for (int i = 0; i < n-1; i++){
int a, b; cin >> a >> b; a--; b--;
con[a]++; con[b]++;
adj[a].push_back(b);
adj[b].push_back(a);
}
queue<int> q;
// add leaves to the q for bfs
// make 0 the root
for (int i = 0; i < n; i++){
if (con[i] == 1 && i != 0) q.push(i);
}
// give and take to/from parent for the answer
vector<ans> give;
vector<ans> take;
while (!q.empty()){
int cur = q.front();
q.pop();
for (int i : adj[cur]){
if (con[i] == 1 && i != 0) continue;
con[i]--;
if (bales[cur] > avg){
// give case
give.push_back({cur+1, i+1, bales[cur]-avg});
}
else if (bales[cur] < avg){
// take case
take.push_back({i+1, cur+1, avg-bales[cur]});
}
bales[i] += bales[cur]-avg;
// only add i if its a leaf
if (con[i] == 1 && i != 0) q.push(i);
}
}
// reverse take to avoid negatives
reverse(take.begin(), take.end());
cout << (int)give.size()+(int)take.size() << endl;
for (auto i : give){
cout << i.startbarn << " " << i.endbarn << " " << i.baleamt << endl;
}
for (auto i : take){
cout << i.startbarn << " " << i.endbarn << " " << i.baleamt << endl;
}
}
Thanks for reading this! Downvote me if you want but know I tried my best this time.
