Continuing the discussion from STICNOT - Sticky notes solution?:
Problem Clarification
Given values of N vertex and N-1 edges. You can perform 3 operations.
- Swap vertex value
- Swap edges value
- Change vertex value - cost 1 coin per action.
You need to make all adjacent vertex values greater than or equal to the edge value i.e. av \ge be
Find out the minimum number of coins you need to satisfy the required condition.
Solution Explanation
Every edge value need two greater or equal vertex value.
To check it, we can use priority_queue.
- Take input and store edge and vertex value in a priority_queue, say
priority_queue<int> a, b;[a for vertex value, b for edge value].
Code example:
int n;
cin >> n;
priority_queue<int> a, b;
for (int i = 1, x, y, d; i < n; i++) {
cin >> x >> y >> d;
b.push(d);
}
for (int i = 0, d; i < n; i++) {
cin >> d;
a.push(d);
}
-
Count how many coins you need to achieve this, say
cnt = 0
Priority_queue keep the maximum value at the top position in c++ (java keep the minimum value at the top position). -
Now checkout the maximum value of edge, if it is greater then the vertex value, then we need 2 coins to get maximum value. i, e,
cnt += 2otherwise pop out the maximum vertex value. Now every edge need one maximum or equal vertex value to satisfy the condition.
Code Example:
int cnt = 0;
if (b.top() > a.top()) {
cnt += 2;
b.pop();
} else {
a.pop();
}
- Now loop throw all edges and check out the condition: av \ge be if condition is false, need one coin to fix it. We always use coin to change minimum vertex value, that’s why we don’t pop out vertex value. Pop out vertex value from a if the condition is true. Here is the code example:
while (!b.empty()) {
if (b.top() > a.top())
cnt++;
else
a.pop();
b.pop();
}
- Now print out the minimum coins (cnt) you need to satisfy the required condition.
cout << cnt << "\n";
That’s all 
Solution Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(a) a.size()
#define all(a) a.begin(), a.end()
#define w(a) std::cerr << #a << " : " << (a) << "\n";
void solve() {
int n;
cin >> n;
priority_queue<int> a, b;
for (register int i = 1, x, y, d; i < n; i++) {
cin >> x >> y >> d;
b.push(d);
}
for (register int i = 0, d; i < n; i++) {
cin >> d;
a.push(d);
}
int cnt = 0;
if (b.top() > a.top()) {
cnt += 2;
b.pop();
} else {
a.pop();
}
while (!b.empty()) {
if (b.top() > a.top())
cnt++;
else
a.pop();
b.pop();
}
cout << cnt << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
register int tc;
cin >> tc;
while (tc--) solve();
return 0;
}
Happy Coding 
It’s also included in this code, When there is only one vertex value is greater than edge value, then we need another maximum value to satisfy the required condition.