Submission #854833

#TimeUsernameProblemLanguageResultExecution timeMemory
854833NeroZeinPapričice (COCI20_papricice)C++17
0 / 110
1 ms4956 KiB
#include "bits/stdc++.h" using namespace std; #ifdef Nero #include "Deb.h" #else #define deb(...) #endif const int N = 2e5 + 5; int sz[N]; vector<int> g[N]; void dfs(int v, int p) { sz[v] = 1; for (int u : g[v]) { if (u != p) { dfs(u, v); sz[v] += sz[u]; } } } int dfs2(int v, int p, int n) { int next = 0; for (int u : g[v]) { if (u != p && sz[u] > sz[next]) { next = u; } } if (sz[v] > n / 3) { return dfs2(next, v, n); } g[p].erase(find(g[p].begin(), g[p].end(), v)); return v; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for(int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } int max_size = 0; int min_size = n; for (int rep = 0; rep < 2; ++rep) { dfs(1, 1); int v = dfs2(1, 1, n); max_size = max(max_size, sz[v]); min_size = min(min_size, sz[v]); if (n != sz[1]) { max_size = max(max_size, sz[1] - sz[v]); min_size = min(min_size, sz[1] - sz[v]); } } cout << max_size - min_size << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...