#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 500010
int N, A, B, X, Y, dist1[MAXN], dist2[MAXN], len[MAXN], cnt[MAXN], L[MAXN];
lld C[MAXN];
vector<int> adj[MAXN];
void dfsMerge(int node, int prev) {
lld maxi1 = 0, maxi2 = 0;
for(auto x : adj[node]) {
if(x != prev) {
dfsMerge(x, node);
if(len[x]+1 >= maxi1) maxi2 = maxi1, maxi1 = len[x]+1;
else if(len[x]+1 >= maxi2) maxi2 = len[x]+1;
}
}
if(maxi2 == 0) return;
L[node] = maxi1+maxi2;
if(maxi1 == maxi2) {
lld sum = 0;
for(auto x : adj[node]) {
if(x != prev) {
if(len[x]+1 == maxi1) C[node] -= cnt[x]*cnt[x], sum += cnt[x];
}
}
C[node] += sum*sum;
C[node] /= 2;
} else {
lld cnt1 = 0, cnt2 = 0;
for(auto x : adj[node]) {
if(x != prev) {
if(len[x]+1 == maxi1) cnt1 += cnt[x];
if(len[x]+1 == maxi2) cnt2 += cnt[x];
}
}
C[node] = cnt1*cnt2;
}
}
void dfsDist(int node, int prev, int dist[]) {
dist[node] = dist[prev]+1;
for(auto x : adj[node]) {
if(x != prev) dfsDist(x, node, dist);
}
}
pii dfsMaxPut(int node, int prev) {
cnt[node] = 1;
for(auto x : adj[node]) {
if(x != prev) {
pii cur = dfsMaxPut(x, node);
if(cur.fi+1 > len[node]) {
len[node] = cur.fi+1;
cnt[node] = cur.se;
} else if(cur.fi+1 == len[node]) cnt[node] += cur.se;
}
}
return {len[node], cnt[node]};
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);
cin >> N;
for(int i = 1; i < N; i++) {
int x, y; cin >> x >> y;
adj[x].pb(y); adj[y].pb(x);
}
dist1[1] = -1; dfsDist(1, 1, dist1);
for(int i = 1; i <= N; i++) if(dist1[i] > dist1[A]) A = i;
dist1[A] = -1; dfsDist(A, A, dist1);
for(int i = 1; i <= N; i++) if(dist1[i] > dist1[B]) B = i;
dist2[B] = -1; dfsDist(B, B, dist2);
int rast = INF, prec = 0;
for(int i = 1; i <= N; i++) {
int eks = max(dist1[i], dist2[i]);
prec = max(prec, dist1[i]);
if(eks == rast) Y = i;
else if(eks < rast) X = i, Y = 0, rast = eks;
}
if(prec == N-1) {
cout << 0 << ' ' << 1 << endl;
return 0;
}
PRINT(X);
PRINT(Y);
PRINT(prec);
lld score = 0, Cnt = 0;
if(Y == 0) {
dfsMaxPut(X, X);
dfsMerge(X, X);
for(int i = 1; i <= N; i++) {
if(i != X) {
lld cur = (lld)(prec-len[i])*(L[i]);
PRINT(i);
PRINT(cur);
PRINT(cnt[i]);
PRINT(C[i]);
if(cur > score) {
Cnt = C[i];
score = cur;
} else if(cur == score) Cnt += C[i];
}
}
///PUTEVI KOJI PROLAZE KROZ CENTAR
if(adj[X].size() > 2) {
lld maxi1 = 0, maxi2 = 0, br = 0, cnt1 = 0, cnt2 = 0;
for(auto x : adj[X]) {
if(len[x]+1 > maxi1) maxi2 = maxi1, maxi1 = len[x]+1;
else if(len[x]+1 > maxi2) maxi2 = len[x]+1;
}
for(auto x : adj[X]) {
if(len[x]+1 == maxi1) br++, cnt1 += cnt[x];
if(len[x]+1 == maxi2) cnt2 += cnt[x];
}
if(br <= 2) {
if(maxi1*(maxi1+maxi2) > score) score = maxi1*(maxi1+maxi2), Cnt = cnt1*cnt2;
else if(maxi1*(maxi1+maxi2) == score) Cnt += cnt1*cnt2;
} else {
lld curS = cnt1*cnt1;
for(auto x : adj[X]) {
if(len[x]+1 == maxi1) curS -= cnt[x]*cnt[x];
}
curS /= 2;
if(2*maxi1*maxi1 > score) score = 2*maxi1*maxi1, Cnt = curS;
else if(2*maxi1*maxi1 == score) Cnt += curS;
}
}
///
} else {
dfsMaxPut(X, Y); dfsMaxPut(Y, X);
dfsMerge(X, Y); dfsMerge(Y, X);
for(int i = 1; i <= N; i++) {
lld cur = (lld)(prec-len[i])*(L[i]);
if(cur > score) {
Cnt = C[i];
score = cur;
} else if(cur == score) Cnt += C[i];
}
}
cout << score << ' ' << Cnt << endl;
return 0;
}
Compilation message
road.cpp: In function 'int main()':
road.cpp:3:52: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
^
road.cpp:106:17: note: in expansion of macro 'PRINT'
PRINT(cur);
^~~~~
road.cpp:3:52: warning: format '%d' expects argument of type 'int', but argument 4 has type 'long long int' [-Wformat=]
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
^
road.cpp:108:23:
PRINT(C[i]);
~~~~
road.cpp:108:17: note: in expansion of macro 'PRINT'
PRINT(C[i]);
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
12152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
12152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
12152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
