이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
=======-==========---=-----------------------=-==================-==-=-=-===------------------------------------------------------
---------=--==-------------------------------=----========-----==--=-----=--------------------------------------------------------
--------=====-======-----------=-------------------=---=----=======-------==--------------------:---------------------------------
-------=----===--------------------=-------------==-----------=--------------=---------:-::-:::::::::::::::::::::::::---:::::-:::-
----------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------:------:-------------------:::--------:-------------------:-:-
---------------:----------------------------------------:------------------------------------:::::::::::::::::----:::-::----------
--------:-::---:::-::::-----------::::::-:---:------:::::--------------:--------::--::::-:::::::::::::::::::::::::::::::-:::------
-------------------:::::::--------::-:::::::::---=+***++=++=----------:--::::::--:::::::-:::------:::--:::::---::::::::::---------
:::::::-::::--:::::::::::::::::::::::::::::--#%%@@@@@@@@@@@%+----------::------:::::::::::::::::-:-:-::::::::::::::-::-:---::-::--
::-:::::::---::::::::::----:--:-:-:::::---:=%@@@@@@@@@@@@@@@@*=--+------:::::::::::::::::::-::-:::--------:::::::::-::::::--------
::::::-:::::::::::::::::::::::::::::::::::-*%@@@@@@@@@@@@@@%*=*@@@@#+=-:::::::::::::::::::::::::::::::-::=*%%@@@@%#*=--::--::-----
::::::::::::::::::::::::::::::::::::::::::+#=%@@@@@@@@@@@@@@%@@@@@@@%#+=----:::::::::::::::::::::::::::=%@@@@@@@@@@@@%=::---------
::::::::::::::::::::::::::::--::::::::::::-@*+@@@@@@@@@@@@@@@@@@@%*+==========------::::::::::::::::::+@@@@@@@@@@@@@@@@+::-----:::
::::::::::::::::::::::::::::-------------::-+:=#%@%%%@@%@@@@@@@@*+=========+=========-::::::::::::::-*@@@@@%@%%%%%#%@@@@*-::::::::
:::::::::-:::::::::::::::::::::::::::::::::::-*#######%%@@@@@@@+=+++++++++***++*+**++*+:::::::::::==#@@@@@@@@@@@@@@%%#@@@+:::::::-
:::::::::::::::::::::::::::::::::::::::::::::-:--%%###%%@@@@@@%#**#****#%%%%%#%%####****-::::::::-+%@@@@@@@@@@@@@@@%@@@@@@=:------
:::::::::::::::.:::::::::::::::::::::::::::::::::++###%@@@@@%%%%%@%%###%%@@@@@@@@@@@%%###+::::::::%@@@@@@@@@@@@@@%**@@@@@@@=::::::
::::::::::::::..........::::::::::::::::::::::::::::-*%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%#:..::=%@@@@@@@@@@@@@@@@@@@@@@@@@@=:::::
:::::::::::::::::::.::::::::::::::::::::::::::::::::::---%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:.=#@@%#%@@@@@@@@@@@@@@@@@@@@@@@@*:::.
:::::::::::::::::::::::::::::::::::::::.....:::.........@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#.:+%@@@@@@%#*+========++**###@@#*=...
:::::::::::::::::::::::::::::::::::::::::.:::.:.........%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#..:+*#%@@@@@@@@@@@@@@@@@@@@@@@#+:...
::::::::::::::::::...:...:::..::.:....:......:+-........+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#......:=**#%%%%%%%%@%%##*+=::::....
::::::::::::::::.............................-=:..::...-%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#...........:-=:..............::::.
.....::::::::.............................:-:........:.*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%:........+*#+..............::..:-
......:..::..:..........................::--:........::#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%-...:=++#%@=====:...............
:::.:::::::::::........................::::---::...::.:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+*:-+=++#%#+++*++***+=::.......:
::.:::::::::::..:...................::::::--=-:......*@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@**-=+++#%*++**+=--=+++**+-:...=
::::::::.....:......::...........:::::::-::---::::::=@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@*#+=++*#+++****+==+===+++**=-.
:.:..:::::.:::.................:::::::-:::----:-:::-%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%*##++**++****###%%#*++***+===
:::::::::::::.::...............:--::--::::====-::=+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@*#****+***##*#%%#***=+===
:::::::::::::.::.:..:..........:::::---:::--=---==%@@@@@@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%##%##**++*#******++++++
..........................:::::..::::--:---==--:%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%#***#%######**+
.......::...............:::.:.....:::----====-:.@@@@@@@@@@@@@%%@@@%#%@@%@@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%######*+:::---:
......::::::::::::::.::.::.:....::::....--+-*=::@@@@@@@@@@-....+%%%##%@@@%%%%%@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@=-==---=-:.........
...:::::::.:::::::.:::.:........::......::::-:..-=+*#%@@@@#+-::-%@@@%%%%%#%@@@@@@@**%@@@@@@@@@@@@@@@@@@@@@@@@@#:-:..............::
::::::::::::::::.:-=-::........:::............:::=....-=+*##%%%%@@@@@@@@@@@@@@@@@%+*+@@@@@@@@@@@@@@@@@@@@@@@@@:..-:.......:-:----:
:::::::::::::::.:-==:.........::..::-::....-=++*++*+++=+++*#@@@@@@@@@@@@@@@%%@@@@@#@#@@@@@@@@@@@@@@@@@@@@@@%%+.............:-=-:..
.::::::::::::..---=-:::.::.::----=**++=..:==***@%%%%%###*#%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*=::....................
..::::::::::::=====-:::::::--*++=*#**#*..=+**#%@@@%%@%%%#%%%%%@@@@@%@@@@@%%@@@@@@@@@%@@%%%@@@@@@@@@@@@@@@@*..........:::.::.......
:::::::::.::-=+====-:::..::=*####**#%%#..=#**%%%@@@@%%%%%%%%@%%%%%@@@@@%@%%@%%%%%%@%%%%%%%%@@@@@@@@@@@@@@@%-:...........--*#*++---
:::::::::::::-===--:::::::--=*%%%%@@@%#.:=+#%%%@@@@%***##%%@@@@@@@@%%@%@@@@@@%%%#%%%###%%%@@@@@@@@@@@@@@@@@%%#*#=-:..........:...-
::::::::::::::::==--::::-===*##%@@@@@%+.=######%%#+#*++++#%++#%%%%@%%@@@@@@@@@@@@@@@%@@@%@@@@@@@@@@@@@@@@@@%%@@@@@*=++==***=-:::-#
.:.::..:::::::::..::::::-+**#%@@@@@@@@=:+###%#%#*==#*****#%+.:*####*=#%%%%%@%%@%%#####**%%%@@@@@@@@@@@@@@@@*@@@@%#%*+*%@@@@@@%#**%
::::::::::::::.....:---==+###%@@@@@@@@=-##%%%###*==##%#####+.:+###*+=%%%%#%**%%#*****+*#%%@@@@@@@@@@@@@@@@@@%@@%%@##%#%%%%%@@@%##*
::::::...::---+:.....=+=*%#%@@@@%%@@@@=+##%%####*=#%@%%%#%%#..=*#*+-#@@@%#++*##*+*=::-*%@@@@@%%#@@@@@@@@@@@@@%#%@@@%%%%@@@%@@@@%#*
:--=-..:=----=-.......=##@@@@@@@@@@@@@**###%####**@@@@@@@@%%..-*#+:#@@@@*=+=:+-:..::=#%%@@%##**@%@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@#
........-++*%=....::::..=%@@@@@@@@@@@@**#######*#@@@@@@@@@@#..:+*-+@@@@%+::.:...--:+%%@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
----+*++**##%+=-..:.:+#*##@@@@@@@@@@@@+#######*#@@@@@@@@@@@+..-++:@@@@#-...::.-=::=%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@
###%*++#@@%@%***%@@%###@@@@%%@@@@@@@@@+########@@@@@@%@@@@@:..-*=+@@@#-:.....:-+**#*#%@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@%%
#===+#%@@@@@@%%@@@@%@@%*-.+:..:+@@@@@%*######*-.:=::..==---..:-*+:.:---...-:=*+=+*###%@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@
.:-::..:-==:...-==-=...........:--::.:######*:..............:=*##*::-=-..-:.=++=*%%%%@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@
.:::--:::-=-.........................=*#####+..........:...-*%@@@+-+@-..:...:=#%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#++=--::-=+@@@@@@@@@@
:::==+****+-:.......................:*######+........+#%*%@@@@@@#-:-#=-#=:.:*%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+=++=++=*##%+@@@@@@@@@
.....:=++**=:..:.:..................-*#%######:.......::+%@@@%#++=-=+%#=..**%%%%@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@%+@@@@@@@@
.........-:...:-...................:+#%##%%%@@%:.........--::::##==.....:-=*##%%##%@@@@@@@@@@@@@@@@@@@@@@@@@@@%%%@%@@@@@@++@@@@@@@
::................................-+*#%%%@@@@@@+......:..:::-:-==.....:+=++*######@@@@@@@@@@@@@@@@@@@@@@@@@@@%%@@@@@@@@@@@*#@@@@@@
...........................:-=+=..=*%@@@@@@@@%=...:........---+*=:..:=+-*#@@@%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#@@@@@@
........................-##=*%@@@@@@@@@%+-:+@@#-..:--::::...:=+::==**#*#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
:......................:++===##%%%%%*=:..-#**%#**--**-::..=*##==*%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
=-..................................::---==+=:::-+#%@%%##%%#@@@#%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
+*-...............................................-#@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#=-=*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
............................................:+#*==+--=----=*##@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%++=....:+@@@@@@@@@@@@@@@@@@@%%%*+-.:--
*/
// Ahmadov orz
/// successful failure
#include <bits/stdc++.h>
/// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
/// using namespace __gnu_pbds;
#define int long long
#define pb push_back
#define pii pair<int, int>
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define drop(x) cout<<x<<endl;return
// template <class T>
// using isTree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/// sometimes you gotta think simple
struct custom_hash {
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
x ^= FIXED_RANDOM;
return x ^ (x >> 16);
}
};
const int N = 1e5 + 7;
vector <int> g[N];
int val[N];
int dp[N];
int ans = 0;
void dfs(int node, int par = -1, int k = 0)
{
priority_queue <int> pq;
//vector <int> subtrees;
dp[node] = val[node];
for (auto v:g[node]) {
if (par != v) {
dfs(v, node, k);
dp[node] += dp[v]; // dfs atandan sonra et!!!
pq.push(dp[v]); // dfs atandan sonra et!!!
//subtrees.pb(v);
}
}
// cout << "node: " << node << endl;
// cout << "subtree: ";
// for (auto u:subtrees) {
// cout << u << " ";
// }
// cout << endl;
// cout << endl;
while (!pq.empty() && dp[node] > k) {
ans++;
dp[node] -= pq.top();
pq.pop();
}
}
void failure()
{
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> val[i];
}
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1, -1, k);
// cout << "! ";
// for (int i = 1; i <= n; i++) {
// cout << dp[i] << " ";
// }
// cout << endl;
drop(ans);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> tt;
while (tt--)
{
failure();
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
