#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 5005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int a[N], n, m, k;
vector<int> edges[N];
int max_distance = 0;
int answer = 0;
vector<int> par[N];
bool used[N];
int dist[N], dp[N];
void solve(int test_case){
int i, j;
cin >> n;
for(i=0;i<n;i++){
int u, v;
cin >> u >> v;
edges[u].pb(v);
edges[v].pb(u);
}
for(int start=1;start<=n;start++){
for(i=1;i<=n;i++){
par[i].clear();
used[i] = false;
dist[i] = 0;
dp[i] = 0;
}
queue<int> q;
q.push(start);
used[start] = true;
vector<int> order;
while(!q.empty()){
auto u = q.front();q.pop();
order.pb(u);
for(auto v : edges[u]){
if(!used[v]){
par[v].pb(u);
used[v] = true;
q.push(v);
dist[v] = dist[u] + 1;
}else if(dist[v] == dist[u] + 1){
par[v].pb(u);
}
}
}
for(i=1;i<=n;i++){
if(chmax(max_distance, dist[i]))
answer = 0;
}
dp[start] = 1;
for(auto u : order){
for(auto v : edges[u]){
//~ assert(par[u].size() <= 2);
if((par[u].size() && par[u][0] != v) && (par[u].size() > 1 && par[u][1] != v))continue;
dp[u] += dp[v];
}if(dist[u] == max_distance)answer += dp[u];
}
//~ cout << "\n\n";
//~ for(i=1;i<=n;i++)cout << dist[i] << ' ';cout << '\n';
//~ for(i=1;i<=n;i++)cout << dp[i] << ' ';cout << '\n';
//~ cout << "when start was " << start << " they were: " << max_distance << ' ' << answer << '\n';
}
assert(answer%2==0);
cout << answer/2 << '\n';
return;
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int _T;
cin >> _T;
for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
shymbulak.cpp: In function 'void solve(int)':
shymbulak.cpp:24:9: warning: unused variable 'j' [-Wunused-variable]
24 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
1004 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
31 ms |
1276 KB |
Execution killed with signal 6 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1004 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
