Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n,m,a,b,v;
- #define MAXN 1000069
- int syny[MAXN];
- int fath[MAXN];
- long long sumDown[MAXN];
- long long mainDist[MAXN];
- int deg[MAXN];
- void DFS (int node, vector <vector <int> > &G, vector <bool> &V)
- {
- V[node] = true;
- for (auto nei:G[node]) if (V[nei] == false)
- {
- fath[nei] = node;
- DFS(nei, G, V);
- }
- }
- void DFS_Ans (int node, vector <vector <int> > &G, vector <bool> &V)
- {
- V[node] = true;
- for (auto nei:G[node]) if (V[nei] == false)
- {
- if (fath[nei] != -1)
- {
- mainDist[nei] = mainDist[node] + n - 2*syny[nei];
- }
- DFS_Ans(nei, G, V);
- }
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- for (int i=0; i!=MAXN; ++i)
- {
- syny[i] = 1;
- fath[i] = -1;
- sumDown[i] = 0;
- mainDist[i] = 0;
- deg[i] = 0;
- }
- cin >> n;
- m = n - 1;
- vector <vector <int> > Graph(n);
- while (m--)
- {
- cin >> a >> b;
- a--,--b;
- Graph.at(a).push_back(b);
- Graph.at(b).push_back(a);
- deg[a]++;
- deg[b]++;
- }
- vector <bool> Vis(n, false);
- DFS(0, Graph, Vis);
- queue <int> Q;
- for (int i=1; i!=n; ++i) if (deg[i] == 1) Q.push(i), sumDown[i] = 0;
- vector <int> TopOrd;
- while (Q.size())
- {
- v = Q.front();
- Q.pop();
- TopOrd.push_back(v);
- if (fath[v] == -1) continue;
- deg[fath[v]]--;
- if (deg[fath[v]] < 2) Q.push(fath[v]);
- }
- for (auto node:TopOrd)
- {
- for (auto nei:Graph[node]) if (nei != fath[node]) syny[node] += syny[nei], sumDown[node] += sumDown[nei] + syny[nei];
- // cout << syny[node] << ", " << sumDown[node] << endl;
- }
- mainDist[0] = sumDown[0];
- for (int i=0; i!=n; ++i) Vis[i] = false;
- DFS_Ans(0, Graph, Vis);
- //for (int i=0; i!=n; ++i) cout << mainDist[i] << " ";
- long long mV = -1;
- for (int i=0; i!=n; ++i) mV = max(mV, mainDist[i]);
- for (int i=0; i!=n; ++i)
- {
- if (mV == mainDist[i])
- {
- cout << i + 1;
- return 0;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement