Submission #1228811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228811		rcll	Hard route (IZhO17_road)	C++20	100 / 100	632 ms	97976 KiB

road

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,dp[500005],cnt[500005],res=0,way=1;
vector<int> adj[500005];

void init(int u,int p){
    cnt[u]=1;
    for (auto x : adj[u]){
        if (x==p) continue;
        init(x,u);
        if (dp[x]+1==dp[u]) {
            cnt[u]+=cnt[x];
        }
        if (dp[x]+1>dp[u]) {
            cnt[u]=cnt[x];
        }
        dp[u]=max(dp[u],dp[x]+1);
    }
}

bool cmp (int& i,int& j){
    return dp[i]>dp[j];
}

void rr(int u,int p){
    sort(adj[u].begin(),adj[u].end(),cmp);
    if (adj[u].size() >= 3){
        int cur=0,cn=0;
        int a=dp[adj[u][0]]+1,b=dp[adj[u][1]]+1,c=dp[adj[u][2]]+1;
        cur=a * (b+c);
        int ca=0;
        for (auto x : adj[u]){
            if (dp[x]+1==c) cn+=ca * cnt[x];
            if (dp[x]+1==b) ca+=cnt[x];
        }
        if (cur>res) res=cur,way=cn;
        else if (cur==res) way+=cn;
    }
    pair<int,int> f={0,1},s={0,0};
    for (auto x : adj[u]){
        if (dp[x]+1>f.first) {
            s=f,f={dp[x]+1,cnt[x]};
        } else if (dp[x]+1==f.first) {
            f.second+=cnt[x];
        } else if (dp[x]+1>s.first) {
            s={dp[x]+1,cnt[x]};
        } else if (dp[x]+1==s.first) {
            s.second+=cnt[x];
        }
    }
    int tmpdp=dp[u],tmpcnt=cnt[u];
    for (auto x : adj[u]){
        if (x==p) {
            continue;
        }
        dp[u]=f.first,cnt[u]=f.second;
        if (dp[x]+1==f.first && cnt[x]==f.second) {
            dp[u]=s.first,cnt[u]=s.second;
        } else if (dp[x]+1==f.first && cnt[x] != f.second) {
            dp[u]=f.first,cnt[u]=f.second - cnt[x];
        }
        rr(x,u);
    }
    dp[u]=tmpdp,cnt[u]=tmpcnt;
}

signed main() {
    cin >> n;
    for (int i=1; i<n; i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    init(1,0);
    rr(1,0);
    cout << res << ' ' << way;
}

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