#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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 N = 5e5 + 7;
const int INF = 1e9 + 7;
int n, m, k;
vector<int> g[N];
int max_distance = 0;
int answer = 0;
int par[N][2];
bool used[N];
int dist[N], dp[N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
memset(used, false, sizeof used);
memset(dp, 0, sizeof dp);
memset(par, 0, sizeof par);
memset(dist, 0, sizeof dist);
queue<int> q;
q.push(i);
used[i] = true;
vector<int> order;
while (!q.empty()) {
auto u = q.front();
q.pop();
order.push_back(u);
for (auto v : g[u]) {
if (!used[v]) {
par[v][0] = u;
used[v] = true;
q.push(v);
dist[v] = dist[u] + 1;
} else if (dist[v] == dist[u] + 1) {
par[v][1] = u;
}
}
}
for (int i = 1; i <= n; i++) {
if (chmax(max_distance, dist[i]))
answer = 0;
}
dp[i] = 1;
for (auto u : order) {
for (auto v : g[u]) {
if (par[u][0] != v && par[u][1] != v)
continue;
dp[u] += dp[v];
}
if (dist[u] == max_distance)
answer += dp[u];
}
}
cout << answer / 2 << "\n";
return 0;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
20332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
20460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1569 ms |
22764 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
