Submission #19540780

---

Source Code Expand

/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan Choudhary (@aryanc403)
*/

#ifdef ARYANC403
    #include "/home/aryan/codes/PastCodes/template/header.h"
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    #pragma GCC optimize ("-ffloat-store")
    #include<iostream>
    #include<bits/stdc++.h>
    #define dbg(args...)
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;


const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vector<vi> e;
    lli A,B;
    vector<ii> cc;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

void dfs0(lli u,lli p)
{
    if(sz(e[u])==1)
        return;
    lli cnt=0;
    for(auto x:e[u])
    {
        if(x==p)
            continue;
        dfs0(x,u);
        cnt++;
    }
    A+=cnt/2;
    cnt%=2;
    if(p==-1&&cnt)
        A++;
    return;
}

//len,mx.
ii dfs(lli u,lli p)
{
    if(sz(e[u])==1)
        return {1,0};
    vi b;
    lli mx=0;
    for(auto x:e[u])
    {
        if(x==p)
            continue;
        cc[x]=dfs(x,u);
        dbg("ret",x,cc[x]);
        b.pb(cc[x].X);
        mx=max(mx,cc[x].Y);
    }

    sort(all(b));
    lli i=0,j=sz(b)-1;
    while(i<j)
    {
        mx=max(mx,b[i]+b[j]);
        i++;
        j--;
    }

    if(i==j)
        return {b[i]+1,mx};
    return {1,mx};
}

lli gt(const vi &x,const vi &y)
{
    return max({x[1],y[1],x[0]+y[0]});
}

void dfs2(lli u,lli p,ii pu)
{
    if(u==-1)
        return;
    dbg(u,pu,"ent");
    if(sz(e[u])==1)
    {
        B=min(B,max(pu.Y,pu.X));
        return;
    }

    vector<vi> bb;
    for(auto x:e[u])
    {
        if(x==p)
        {
            if(pu.X)
                bb.pb({pu.X,pu.Y,-1});
            continue;
        }
        bb.pb({cc[x].X,cc[x].Y,x});
    }

    sort(all(bb));

    const lli n=sz(bb);
    lli i=0,j=n-1,cur=0;
    while(i<j)
    {
        cur=max(cur,bb[i][1]);
        cur=max(cur,bb[j][1]);
        cur=max(cur,bb[i][0]+bb[j][0]);
        i++;
        j--;
    }

    if(i==j)
        cur=max({cur,bb[i][0],bb[i][1]});
    B=min(B,cur);
    dbg(u,cur,bb);
    map<lli,lli> mm,pr;
    mm[0]++;
    i=1,j=n-1;
    while(i<j)
    {
        mm[gt(bb[i],bb[j])]++;
        pr[i]=j;pr[j]=i;
        i++;j--;
    }

    for(lli i=0;i<n;++i)
    {
        lli mx=mm.rbegin()->X;
        lli rem=1;
        if(n%2==0)
        {
            lli v=n/2;
            if(i>=n/2)
                v--;
            rem=1+bb[v][0];
            mx=max(mx,bb[v][1]);
        }

        dfs2(bb[i][2],u,{rem,mx});
        if(pr.find(i+1)!=pr.end())
        {
            const lli g=pr[i+1];
            del(mm,gt(bb[i+1],bb[g]));
            pr.erase(g);
            pr.erase(i+1);
            mm[gt(bb[i],bb[g])]++;
            pr[g]=i;
            pr[i]=g;
        }
    }
}



int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{

    cin>>n;
    e.resize(n);
    cc.resize(n);
    fo(i,n-1)
    {
        cin>>u>>v;
        u--;v--;
        e[u].pb(v);
        e[v].pb(u);
    }

    if(n==2)
    {
        cout<<"1 1"<<endl;
        return 0;
    }

    lli rt=0;
    fo(rt,n)
    {
        if(sz(e[rt])==1)
            continue;
        break;
    }

    dfs0(rt,-1);
    B=INF;
    dfs(rt,-1);
    dfs2(rt,-1,{0,0});
    cout<<A<<" "<<B<<endl;
}   aryanc403();
    return 0;
}

Submission Info

Judge Result