#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MOD = 120734269;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
if(p==0) return 1 % MOD;
int r = bm(b, p >> 1);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
int inv(int b) {
return bm(b, MOD-2);
}
int fastlog(int x) {
return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
deque<bool>dq[MAXN];//the string itself
unordered_set<int>palin[MAXN];//set of hashes of palindromes, at most add 1 each time
deque<int32_t>sufpal[MAXN];//lengths of suffix palindromes
deque<int32_t>prepal[MAXN];//lengths of prefix palindromes
int dsu[MAXN];
int l[MAXN], r[MAXN];// Actual [l,r] ranges
int pos[MAXN],neg[MAXN];
int set_of(int u){
if(dsu[u]==u) return u;
return dsu[u]=set_of(dsu[u]);
}
void union_(int u,int v){
dsu[set_of(u)]=set_of(v);
}
int n;
vector<int>ps_l[MAXN],ps_r[MAXN];
int h(int i, int l, int r) {
if(r < 0) {
int v = (ps_l[i][-l] - ps_l[i][-r - 1] + MOD) % MOD;
v *= pos[-l];
v %= MOD;
return v;
}
else if(l < 0 && r >= 0) {
int v = (ps_l[i][-l] - ps_l[i][0] + MOD) % MOD;
v *= pos[-l];
v %= MOD;
int w = ps_r[i][r] * pos[-l];
w %= MOD;
v += w;
v %= MOD;
return v;
}
else {
int v = (ps_r[i][r] - (l==0? 0: ps_r[i][l-1]) + MOD) % MOD;
v *= neg[l];
v %= MOD;
return v;
}
}
void to_back(int base,bool x){
dq[base].push_back(x);
ps_r[base].push_back((ps_r[base][r[base]]+(1+(x==1))*pos[r[base]+1])%MOD);
r[base]++;
while(sufpal[base].size()){
int lb,rb;
int bruh=sufpal[base].back();
sufpal[base].pop_back();
if(bruh%2==1)lb=bruh/2,rb=bruh/2+1;
else lb=rb=bruh/2;
int x=r[base]-rb;
rb+=x,lb-=x;
if(lb<l[base])continue;
if(dq[base][lb-l[base]]!=dq[base][rb-l[base]])continue;
sufpal[base].push_back(bruh);
break;
}
if(dq[base].size()>1&&dq[base][dq[base].size()-2] == dq[base].back()){
sufpal[base].push_front(r[base] + r[base]-1);
}
sufpal[base].push_front(r[base] + r[base]);
int lb=sufpal[base].back()/2, rb=(sufpal[base].back()+1)/2;
int xx=r[base]-rb;
rb+=xx, lb-=xx;
//[lb,rb] is maximum suffix palindrome, update palin
int hash = h(base,lb,rb);
if(palin[base].count(hash)) return;
palin[base].insert(hash);
}
void to_front(int base,bool x){
}
void solve(int tc) {
cin >>n;
for(int i=1;i<=n;i++) {
dsu[i]=i;
l[i]=r[i]=0;
}
pos[0]=neg[0]=1;
for(int i=1;i<=n;i++){
pos[i]=(pos[i-1]*3)%MOD;
neg[i]=(neg[i-1]*inv(3))%MOD;
}
for(int i=1;i<=n;i++) {
char x;cin >> x;
dq[i].push_back(x=='1');
palin[i].insert(1+(x=='1'));
sufpal[i].push_back(0);
prepal[i].push_back(0);
ps_l[i].push_back(1+(x=='1'));
ps_r[i].push_back(1+(x=='1'));
}
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
a=set_of(a);
b=set_of(b);
if(dq[a].size()>=dq[b].size() || true){
while(dq[b].size()){
to_back(a,dq[b].front());
dq[b].pop_front();
}
union_(a,b);
dq[set_of(a)].swap(dq[a]);
palin[set_of(a)].swap(palin[a]);
swap(l[set_of(a)],l[a]);
swap(r[set_of(a)],r[a]);
sufpal[set_of(a)].swap(sufpal[a]);
prepal[set_of(a)].swap(prepal[a]);
ps_l[set_of(a)].swap(ps_l[a]);
ps_r[set_of(a)].swap(ps_r[a]);
cout<<palin[set_of(a)].size()<<"\n";
}
else{
while(dq[a].size()){
to_front(b,dq[a].back());
dq[a].pop_back();
}
union_(a,b);
dq[set_of(a)].swap(dq[b]);
palin[set_of(a)].swap(palin[b]);
swap(l[set_of(a)],l[b]);
swap(r[set_of(a)],r[b]);
sufpal[set_of(a)].swap(sufpal[b]);
prepal[set_of(a)].swap(prepal[b]);
ps_l[set_of(a)].swap(ps_l[b]);
ps_r[set_of(a)].swap(ps_r[b]);
cout<<palin[set_of(a)].size()<<"\n";
}
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
212496 KB |
Output is correct |
| 2 |
Correct |
109 ms |
212460 KB |
Output is correct |
| 3 |
Incorrect |
101 ms |
212528 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
212496 KB |
Output is correct |
| 2 |
Correct |
109 ms |
212460 KB |
Output is correct |
| 3 |
Incorrect |
101 ms |
212528 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
202 ms |
242704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
212496 KB |
Output is correct |
| 2 |
Correct |
109 ms |
212460 KB |
Output is correct |
| 3 |
Incorrect |
101 ms |
212528 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
