Submission #564305

#	Time	Username	Problem	Language	Result	Execution time	Memory
564305		urosk	Hard route (IZhO17_road)	C++14	0 / 100	11 ms	15956 KiB

road

// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

#define maxn 500005
ll n;
vector<ll> g[maxn];
ll d[maxn];
void naj(ll u,ll par){
    d[u] = d[par] + 1;
    for(ll s : g[u]){
        if(s==par) continue;
        naj(s,u);
    }
}
ll naj(ll u){
    fill(d,d+maxn,llinf);
    d[u] = -1;
    naj(u,u);
    ll s = u;
    for(ll i = 1;i<=n;i++){
        if(d[i]>d[s]) s = i;
    }
    return s;
}
ll rut = 0;
vector<ll> v;
void froot(ll u,ll par,ll f){
    if(u==f){
        rut = v[sz(v)/2];
        return;
    }
    v.pb(u);
    for(ll s : g[u]){
        if(s==par) continue;
        froot(s,u,f);
    }
    v.popb();
}
ll up[maxn];
pll mx[maxn];
pll c[maxn];
pll mrg(pll a,pll b){
    if(a.fi!=b.fi) return max(a,b);
    return {a.fi,a.sc+b.sc};
}
void dfs(ll u,ll par){
    d[u] = d[par] + 1;
    mx[u] = {0,1};
    for(ll s : g[u]){
        if(s==par) continue;
        dfs(s,u);
        mx[u] = mrg(mx[u],{mx[s].fi+1,mx[s].sc});
    }
}
pll ans = {0,0};
void dfs2(ll u,ll par){
    pll p = {0,0};
    for(ll s : g[u]){
        if(s==par) continue;
        ll x = mx[s].fi+2;
        if(p.fi<x) p = {x,p.fi};
        else if(p.sc<x) p = {p.fi,x};
    }
    c[u] = p;
    p = c[par];
    if(u!=par){
        ll x = p.fi;
        if(p.fi==mx[u].fi+1) x = p.sc;
        up[u] = max(up[par]+1,x);
    }
    p = {0,0};
    for(ll s : g[u]){
        if(s==par) continue;
        ll x = mx[s].fi+1;
        if(x>p.fi) p = {x,p.fi};
        else if(x>p.sc) p = {p.fi,x};
    }
    pll cnt = {0,0};
    for(ll s : g[u]){
        if(s==par) continue;
        ll x = mx[s].fi + 1;
        if(x==p.fi) cnt.fi+=mx[s].sc;
        else if(x==p.sc) cnt.sc+=mx[s].sc;
    }
    if(u==rut){
        ll r = 0;
        pll h = {0,0};
        for(ll s : g[u]){
            ll x = mx[s].fi + 1;
            if(x==p.fi) h.fi++;
            if(x==p.sc) h.sc++;
            if(x!=p.fi&&x!=p.sc){
                r = max(r,x);
                continue;
            }
            if(p.fi==p.sc){
                if(cnt.fi>2&&x==p.fi) r = max(r,x-1);
            }else{
                if(x==p.fi&&cnt.fi>1) r = max(r,x-1);
                else if(x==p.sc&&cnt.sc>1) r = max(r,x-1);
            }
        }
        if(p.fi==p.sc){
            if(h.fi>2) r = p.fi;
        }else{
            if(h.sc>1) r = p.fi;
            if(h.fi>1) r = p.fi;
        }
        up[u] = r;
    }
    if(p.fi!=0&&p.sc!=0){
        if(p.fi!=p.sc){
            pll cur = {up[u]*(p.fi+p.sc),cnt.fi*cnt.sc};
            //cerr<<"u: "<<u<< " "<<cur.fi<< " "<<p.fi<< " "<<p.sc<<" "<<cnt.fi<< " "<<cnt.sc<<endl;
            //cerr<<cur.fi<< " "<<cur.sc<<endl;
            ans = mrg(ans,cur);
        }else{
            pll cur = {up[u]*2*p.fi,0};
            //cerr<<"u: "<<u<< " "<<cur.fi<< " "<<p.fi<< " "<<p.sc<<" "<<cnt.fi<< " "<<cnt.sc<<endl;
            for(ll s : g[u]){
                if(s==par) continue;
                if(mx[s].fi+1==p.fi){
                    cur.sc+=(cnt.fi-mx[s].sc)*mx[s].sc;
                }
            }
            cur.sc/=2;
            //cerr<<cur.fi<< " "<<cur.sc<<endl;
            ans = mrg(ans,cur);
        }
    }
    for(ll s : g[u]){
        if(s==par) continue;
        dfs2(s,u);
    }
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n;
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    ll x = naj(1);
    ll y = naj(x);
    froot(x,x,y);
    fill(d,d+n+1,0);
    dfs(rut,rut);
    dfs2(rut,rut);
    /*
    here;
    cerr<<"rut: "<<rut<<endl;
    for(ll i = 1;i<=n;i++) cerr<<mx[i].fi<< " "<<mx[i].sc<<endl;
    ceri(up,1,n);
    here;
    */
    cout<<ans.fi<< " "<<ans.sc<<endl;
    return 0;
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7

4
1 2
2 3
2 4
*/

• Subtask 1: 0 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48