#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair < int, ll > pil;
const int N = 2e5 + 500;
const int OFF = (1 << 18);
pil add(pil A, pil B){
return {max(A.X, B.X), A.Y * (A.X >= B.X) + B.Y * (B.X >= A.X)};
}
pil mul(pil A, pil B){
return {A.X + B.X, A.Y * B.Y};
}
int un[N], n;
vector < int > v[N];
vector < int > cik;
pil sol = {0, 0};
pil T[2 * OFF], ja[N];
pil f(int x, int lst){
pil dep = {0, 1};
for(int y : v[x]){
if(y == lst || un[y]) continue;
pil nxt = f(y, x);
sol = add(sol, mul(dep, nxt));
dep = add(dep, nxt);
}
dep.X++;
return dep;
}
int bio[N];
stack < int > S;
void dfs(int x, int lst){
if((int)cik.size() != 0) return;
char c; scanf(" %c", &c);
if(bio[x]){
cik.PB(x);
while(S.top() != x){
cik.PB(S.top()); S.pop();
}
return;
}
S.push(x); bio[x] = 1;
for(int y : v[x]){
if(y != lst)
dfs(y, x);
if((int)cik.size() != 0) return;
}
S.pop();
}
pil query(int i, int a, int b, int lo, int hi){
if(lo <= a && b <= hi) return T[i];
if(a > hi || b < lo) return {-N, 0};
return add(query(2 * i, a, (a + b) / 2, lo, hi), query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}
int main(){
scanf("%d", &n);
for(int i = 0;i < n;i++){
int x, y; scanf("%d%d", &x, &y);
v[x].PB(y), v[y].PB(x);
}
dfs(1, 1);
return 0;
for(int x : cik) un[x] = 1;
for(int i = 0;i < OFF;i++)
T[OFF + i].X = -N;
for(int i = 0;i < (int)cik.size();i++){
ja[i] = f(cik[i], cik[i]); ja[i].X--;
T[OFF + i] = {ja[i].X - i, ja[i].Y};
}
for(int i = OFF - 1; i ; i--){
T[i] = add(T[2 * i], T[2 * i + 1]);
}
int kol = (int)cik.size() / 2, m = (int)cik.size();
for(int i = 0;i < m;i++){
pil L = query(1, 0, OFF - 1, max(0, i - kol), i - 1); L.X += i;
pil RR = query(1, 0, OFF - 1, min(m - 1, i + kol - !(m&1)) + 1, m - 1); RR.X += m + i;
sol = add(sol, mul(add(L, RR), ja[i]));
}
printf("%lld\n", sol.Y);
return 0;
}
Compilation message
shymbulak.cpp: In function 'void dfs(int, int)':
shymbulak.cpp:50:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
50 | char c; scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
shymbulak.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
76 | int x, y; scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
8164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
