#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define bg begin
#define ed end
#define ft front
#define bk back
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ers erase
#define all(x) (x).bg() (x).ed()
#define sz(x) (int)(x).size()
#define mtp make_tuple
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define str string
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
const int oo = 1e9 + 5;
const pi M = {1e9 + 7, 1e9 + 9};
const pi base = {37, 127};
const int N = 1e5 + 5;
int n, a[N], p[N], lm[N], rm[N], nxt[N], pos[N], len[N], len1[N], LOG[N];
pi e[N], h[N], h1[N], P[N], c[N][17], c1[N][17];
vi a1;
set<pi> s[N];
int getp(int x) { return x == p[x]? x : p[x] = getp(p[x]); }
void join(int x, int y) {
int px = getp(x), py = getp(y);
p[py] = px;
nxt[rm[px]] = lm[py];
rm[px] = rm[py];
}
void trans() {
FRN(i, n) {
p[i] = lm[i] = rm[i] = i;
nxt[i] = -1;
}
FRN(i, n - 1) join(e[i].st, e[i].nd);
int fp = lm[getp(0)];
WHILE(fp != -1) {
a1.pb(fp);
fp = nxt[fp];
}
FRN(i, n) pos[a1[i]] = i;
vi a2(n);
FRN(i, n) a2[i] = a[i];
FRN(i, n) a[i] = a2[pos[i]];
}
void buildh() {
FRN(i, n) {
h[i].st = (1LL * (i? h[i - 1].st : 0) * base.st + a[i] + 1) % M.st;
h[i].nd = (1LL * (i? h[i - 1].nd : 0) * base.nd + a[i] + 1) % M.nd;
}
FSN(i, n) {
h1[i].st = (1LL * (i + 1 < n? h1[i + 1].st : 0) * base.st + a[i] + 1) % M.st;
h1[i].nd = (1LL * (i + 1 < n? h1[i + 1].nd : 0) * base.nd + a[i] + 1) % M.nd;
}
P[0] = {1, 1};
FOR(i, 1, n) {
P[i].st = 1LL * P[i - 1].st * base.st % M.st;
P[i].nd = 1LL * P[i - 1].nd * base.nd % M.nd;
}
}
pi get(int l, int r) {
pi ans;
ans.st = (h[r].st - 1LL * (l? h[l - 1].st : 0) * P[r - l + 1].st % M.st + M.st) % M.st;
ans.nd = (h[r].nd - 1LL * (l? h[l - 1].nd : 0) * P[r - l + 1].nd % M.nd + M.nd) % M.nd;
return ans;
}
pi get1(int l, int r) {
pi ans;
ans.st = (h1[l].st - 1LL * (r + 1 < n? h1[r + 1].st : 0) * P[r - l + 1].st % M.st + M.st) % M.st;
ans.nd = (h1[l].nd - 1LL * (r + 1 < n? h1[r + 1].nd : 0) * P[r - l + 1].nd % M.nd + M.nd) % M.nd;
return ans;
}
bool check(int l, int r) { return get(l, r) == get1(l, r); }
void buildp() {
FRN(i, n) {
int l = 0, r = min(i, n - 1 - i);
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (check(i - mid, i + mid)) {
len[i] = mid;
l = mid + 1;
}
else r = mid - 1;
}
}
len1[n - 1] = -1;
FRN(i, n - 1) {
len1[i] = -1;
if (a[i] != a[i + 1]) continue;
int l = 0, r = min(i, n - 2 - i);
WHILE(l <= r) {
int mid = l + (r - l) / 2;
if (check(i - mid, i + 1 + mid)) {
len1[i] = mid;
l = mid + 1;
}
else r = mid - 1;
}
}
// FRN(i, n) cerr << a[i];
// cerr << '\n';
// FRN(i, n) {
// cerr << i << " : " << len[i] << ' ' << len1[i] << '\n';
// }
// cerr << get1(2, 3).st << '\n';
// cerr << get(1, 3).st << ' ' << get1(1, 3).st << '\n';
// cerr << '\n';
}
pi best(const pi &a, const pi &b) { return {min(a.st, b.st), max(a.nd, b.nd)}; }
void buildstb() {
FRN(i, n) {
c1[i][0] = {oo, -oo};
c[i][0] = {i - len[i], i + len[i]};
if (len1[i] != -1) c1[i][0] = {i - len1[i], i + 1 + len1[i]};
}
FOR(j, 1, 16)
FRN(i, n) {
if (i + (1 << j) - 1 >= n) break;
c[i][j] = best(c[i][j - 1], c[i + (1 << (j - 1))][j - 1]);
c1[i][j] = best(c1[i][j - 1], c1[i + (1 << (j - 1))][j - 1]);
}
FOR(i, 1, n) LOG[i] = log2(i);
}
pi getc(int l, int r) {
int len = LOG[r - l + 1];
return best(c[l][len], c[r - (1 << len) + 1][len]);
}
pi getc1(int l, int r) {
int len = LOG[r - l + 1];
return best(c1[l][len], c1[r - (1 << len) + 1][len]);
}
pi getl(int l, int r) {
int ln = l, rn = r;
pi ans = {oo, oo};
WHILE(ln <= rn) {
int mid = ln + (rn - ln) / 2;
if (mid - r + mid < l) {
ln = mid + 1;
continue;
}
pi tmp = getc(mid, r);
if (tmp.nd >= r) {
ans = min(ans, {mid, 0});
rn = mid - 1;
}
else ln = mid + 1;
}
if (l == r) return ans;
ln = l, rn = r - 1;
WHILE(ln <= rn) {
int mid = ln + (rn - ln) / 2;
if (mid - r + mid + 1 < l) {
ln = mid + 1;
continue;
}
pi tmp = getc1(mid, r - 1);
if (tmp.nd >= r) {
ans = min(ans, {mid, 1});
rn = mid - 1;
}
else ln = mid + 1;
}
return ans;
}
pi getr(int l, int r) {
int ln = l, rn = r;
pi ans = {0, 0};
WHILE(ln <= rn) {
int mid = ln + (rn - ln) / 2;
if (mid + mid - l > r) {
rn = mid - 1;
continue;
}
pi tmp = getc(l, mid);
if (tmp.st <= r) {
ans = max(ans, {mid, 0});
ln = mid + 1;
}
else rn = mid - 1;
}
if (l == r) return ans;
ln = l, rn = r - 1;
WHILE(ln <= rn) {
int mid = ln + (rn - ln) / 2;
if (mid + 1 + mid - l > r) {
rn = mid - 1;
continue;
}
pi tmp = getc1(l + 1, mid);
// cerr << mid << " : " << tmp.st << '\n';
if (tmp.st <= l) {
ans = max(ans, {mid, 1});
ln = mid + 1;
}
else rn = mid - 1;
}
return ans;
}
void join1(int x, int y) {
int px = getp(x), py = getp(y);
// cerr << lm[px] << ' ' << rm[px] << " - " << lm[py] << ' ' << rm[py] << '\n';
if (rm[px] - lm[px] > rm[py] - lm[py]) {
FOR(i, lm[py], rm[py]) {
pi tmp = getl(lm[px], i);
s[px].ins(get(tmp.st - i + tmp.st + tmp.nd, i));
}
p[py] = px;
rm[px] = rm[py];
}
else {
FOR(i, lm[px], rm[px]) {
pi tmp = getr(i, rm[py]);
s[py].ins(get(i, tmp.st + tmp.st - i + tmp.nd));
}
p[px] = py;
lm[py] = lm[px];
}
}
void ansq() {
// pi tmp = getc(0, 2);
// cerr << tmp.st << ' ' << tmp.nd << '\n';
FRN(i, n) {
p[i] = i;
lm[i] = rm[i] = pos[i];
s[i].ins(get(i, i));
}
FRN(i, n - 1) {
join1(e[i].st, e[i].nd);
cout << sz(s[getp(e[i].st)]) << '\n';
// exit(0);
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen(file".inp", "r", stdin);
// freopen(file".out", "w", stdout);
cin >> n;
FRN(i, n) {
char c;
cin >> c;
a[i] = c - '0';
}
FRN(i, n - 1) {
cin >> e[i].st >> e[i].nd;
--e[i].st;
--e[i].nd;
}
trans();
buildh();
buildp();
buildstb();
ansq();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
47600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
5076 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
