Submission #935331

#	Time	Username	Problem	Language	Result	Execution time	Memory
935331		Darren0724	Hard route (IZhO17_road)	C++17	0 / 100	2 ms	608 KiB

road

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
const int N=5005;
const int INF=1e9;
const int mod=1e9+9;
int n,ans=0,cnt=0;
vector<int> adj[N];
vector<int> deep(N),deg(N);
vector<int> dp1(N),dp2(N);
void upd(int i,int k){
    if(dp1[i]<k){
        dp2[i]=dp1[i];
        dp1[i]=k;
    }
    else if(dp2[i]<k){
        dp2[i]=k;
    }
}
void updans(int k,int cnt1){
    if(ans==k){
        cnt+=cnt1;
    }
    else if(k>ans){
        ans=k;
        cnt=cnt1;
    }
}
void dfs(int k,int pa) {
    for(int j:adj[k]){
        if(j==pa)continue;
        deep[j]=deep[k]+1;
        dfs(j,k);
        upd(k,dp1[j]);
    }
    updans(dp2[k]*(dp1[k]-deep[k]),1);
    if(dp1[k]==dp2[k])updans(dp2[k]*(dp1[k]-deep[k]),1);
    if(deg[k]==1)upd(k,deep[k]);
}
// deep[j]*deep[j1]
int32_t main() {
    LCBorz;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        deg[a]++,deg[b]++;
    }
    for(int i=1;i<=n;i++){
        if(deg[i]==1){
            dp1.assign(N,-INF);
            dp2.assign(N,0);
            deep.assign(N,0);
            dfs(i,i);
        }
    }    
    cout<<ans<<' '<<cnt/2<<endl;

    return 0;
}

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