Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <map>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <cstring>
- #include <queue>
- #define ll long long
- #define ld double
- #define pb push_back
- #define ft first
- #define sd second
- #define inf ((ll)1e17)
- #define mod (1e9+7)
- #define eps (-1e7)
- using namespace std;
- vector <ll> g[600000];
- ll dup[600000],d[600000],p[600000];
- bool u1[600000],u2[600000];
- void dfs1(ll v) {
- u1[v] = 1;
- ll kol = 0;
- for (auto to: g[v]) {
- if (!u1[to]) {
- p[to] = v;
- dfs1(to);
- d[v] = max(d[v],d[to]);
- kol++;
- }
- }
- if (kol != 0)
- d[v]++;
- }
- void dfs2(ll v,ll mx=0) {
- u2[v] = 1;
- dup[v] = max(dup[v],mx);
- vector <ll> ver;
- for (auto to: g[v]) {
- if (!u2[to]) {
- ver.pb(to);
- }
- }
- vector <ll> mpref(ver.size()+1),msuff(ver.size()+1);
- for (ll i = 0; i < ver.size(); i++) {
- if (i==0) {
- mpref[i] = d[ver[i]]+1;
- }
- else {
- mpref[i] = max(mpref[i-1],d[ver[i]]+1);
- }
- }
- for (ll i = (ll)ver.size()-1; i >= 0; i--) {
- if (i == (ll)ver.size()-1) {
- msuff[i] = d[ver[i]]+1;
- }
- else {
- msuff[i] = max(msuff[i+1],d[ver[i]]+1);
- }
- }
- ll ind = 0;
- for (auto to: g[v]) {
- if (!u2[to]) {
- dup[to] = dup[v]+1;
- ll k1 = 0;
- if (ind > 0)
- k1 = mpref[ind-1];
- ll k2 = 0;
- if (ind+1<ver.size())
- k2 = msuff[ind+1];
- dfs2(to,max(k1,k2)+1);
- ind++;
- }
- }
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie();
- cout.tie();
- //freopen("c.in","r",stdin);
- //freopen("c.out","w",stdout);
- ll n;
- cin >> n;
- for (ll i = 1; i < n; i++) {
- ll a ,b;
- cin >> a >> b;
- g[a].pb(b);
- g[b].pb(a);
- }
- p[1] = 1;
- dfs1(1);
- dfs2(1);
- ll ans = inf;
- ll ver = 0;
- for (ll i = 1; i <= n; i++) {
- ll cur = 0;
- for (auto x: g[i]) {
- if (x != p[i]) {
- cur += (d[x] + 1) * (d[x] + 1);
- }
- }
- ll mn = dup[i]-1;
- cur += (mn+1)*(mn+1);
- if (ans > cur) {
- ans = cur;
- ver = i;
- }
- }
- cout << ans << ' ' << ver;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement