#include <bits/stdc++.h>
using namespace std;
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a))
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int mxN=3e5+5;
vector <vector<int>> adj(mxN);
int dist[mxN];
void dfs(int node, int par){
for(auto x:adj[node]){
if(x != par){
dist[x] = dist[node]+1;
dfs(x, node);
}
}
}
int dfs2(int node, int par, int workers=0){
if(adj[node].size() - (node != 1) == 0)
return 0;
ll temp, ret=0;
temp = (adj[node].size() - (node != 1) - workers)/(dist[node]+1) + ((adj[node].size()-(node != 1)-workers)%(dist[node]+1) != 0);
for(auto x:adj[node]){
if(x != par){
ret += dfs2(x, node, temp);
}
}
return temp + ret;
}
int main(){
// amount of workers needed=ceil(amount of children/distance) + answer for each subtree
// so idea is simple like
// we will solve each subtree seperately
// for each subtree answer will be equal to:
// workers_needed - workers_assigned
// 1
// / \
//2 3
int n;
cin >> n;
for(int i=0; i<n-1; i++){
int x, y;
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, -1);
cout << dfs2(1, -1);
}
Compilation message
luk.cpp:57:5: warning: multi-line comment [-Wcomment]
57 | // / \
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
7296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
7368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
7364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
7380 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
7764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
26 ms |
8788 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
106 ms |
12108 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
261 ms |
17216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
328 ms |
22276 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
340 ms |
22280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |