Link to the problem:↵
https://codeforces.net/contest/741/problem/D↵
↵
I came up with a solution using Small To Large and Xor Hashing, but my time complexity is $O(n*log^2(n)*26)$, which is still not optimized enough. It got the extra $log$ from using ```map```, and I'm not sure of how to get rid of the ```map```. Can someone help me pls?↵
↵
↵
<spoiler summary="My Code (I switched to unordered_map and it still TLEs)">↵
```c++↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
//#define int long long //emergency debug↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef pair<ii,int> iii;↵
#define f first↵
#define s second↵
#define pb push_back↵
#define mp make_pair↵
#define hellnah cout<<"NO\n"↵
#define fuckyeah cout<<"YES\n"↵
#define en '\n'↵
↵
↵
const ll oo = 1e9;↵
const ll mod = 1e9+7;↵
↵
↵
int n;↵
vector<ii> g[500005];↵
int b[500005];↵
int hv[500005];↵
int rnk[500005];↵
int dp[500005];↵
int sz[500005];↵
↵
↵
↵
void dfs(int u){↵
sz[u] = 1;↵
ii tmp = mp(0,0);↵
for(ii p : g[u]){↵
int v = p.f;↵
int x = p.s;↵
rnk[v] = rnk[u]+1;↵
b[v]=b[u]^x;↵
dfs(v);↵
sz[u]+=sz[v];↵
tmp = max(tmp,mp(sz[v],v));↵
}↵
↵
hv[u] = tmp.s;↵
}↵
↵
void hld(int u, vector<int> &sub, unordered_map<int,int> &s){↵
↵
↵
if(hv[u]){↵
hld(hv[u],sub,s);↵
dp[u] = dp[hv[u]];↵
for(int i = 0;i<26;i++){↵
int x = b[u]^(1<<i);↵
if(s.find(x)!=s.end())↵
dp[u] = max(dp[u], s[x]-rnk[u]);↵
}↵
if(s.find(b[u])!=s.end())↵
dp[u] = max(dp[u], s[b[u]]-rnk[u]);↵
}↵
↵
s[b[u]] = max(s[b[u]], rnk[u]);↵
sub.pb(u);↵
↵
↵
↵
↵
for(ii p : g[u]){↵
int v = p.f;↵
if(v==hv[u]) continue;↵
↵
vector<int> sub2;↵
unordered_map<int,int> s2;↵
s2.reserve(sz[v]);↵
hld(v, sub2, s2);↵
dp[u] = max(dp[u], dp[v]);↵
↵
for(int x : sub2){↵
int k = b[x];↵
for(int i = 0;i<26;i++){↵
int tmp = k^(1<<i);↵
if(s.find(tmp)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[tmp]-rnk[u]*2);↵
}↵
if(s.find(k)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[k]-rnk[u]*2);↵
↵
}↵
for(int x : sub2){↵
sub.pb(x);↵
s[b[x]] = max(s[b[x]], rnk[x]);↵
}↵
}↵
}↵
↵
↵
int32_t main(){↵
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
// #ifndef ONLINE_JUDGE↵
// freopen("abc.inp","r",stdin);↵
// freopen("abc.out","w",stdout);↵
// #endif↵
↵
cin>>n;↵
for(int i = 2;i<=n;i++){↵
int u; char c;↵
cin>>u>>c;↵
int x = (1<<(c-'a'));↵
g[u].pb(mp(i,x));↵
}↵
↵
↵
rnk[1] = 1;↵
dfs(1);↵
↵
↵
vector<int> sub;↵
unordered_map<int,int> s;↵
↵
s.reserve(n);↵
hld(1, sub, s);↵
for(int i = 1;i<=n;i++) cout<<max(dp[i],0)<<' '; cout<<en;↵
↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
↵
↵
EDIT: Got rid of the ```map```, not sure how to explain it tho. And the solution above would've WAed test 32 because i forgot to make the default value of the map to be ```-INF```↵
↵
Accepted solution: https://codeforces.net/contest/741/submission/287930415↵
https://codeforces.net/contest/741/problem/D↵
↵
I came up with a solution using Small To Large and Xor Hashing, but my time complexity is $O(n*log^2(n)*26)$, which is still not optimized enough. It got the extra $log$ from using ```map```, and I'm not sure of how to get rid of the ```map```. Can someone help me pls?↵
↵
↵
<spoiler summary="My Code (I switched to unordered_map and it still TLEs)">↵
```c++↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
//#define int long long //emergency debug↵
↵
typedef long long ll;↵
typedef pair<int,int> ii;↵
typedef pair<ii,int> iii;↵
#define f first↵
#define s second↵
#define pb push_back↵
#define mp make_pair↵
#define hellnah cout<<"NO\n"↵
#define fuckyeah cout<<"YES\n"↵
#define en '\n'↵
↵
↵
const ll oo = 1e9;↵
const ll mod = 1e9+7;↵
↵
↵
int n;↵
vector<ii> g[500005];↵
int b[500005];↵
int hv[500005];↵
int rnk[500005];↵
int dp[500005];↵
int sz[500005];↵
↵
↵
↵
void dfs(int u){↵
sz[u] = 1;↵
ii tmp = mp(0,0);↵
for(ii p : g[u]){↵
int v = p.f;↵
int x = p.s;↵
rnk[v] = rnk[u]+1;↵
b[v]=b[u]^x;↵
dfs(v);↵
sz[u]+=sz[v];↵
tmp = max(tmp,mp(sz[v],v));↵
}↵
↵
hv[u] = tmp.s;↵
}↵
↵
void hld(int u, vector<int> &sub, unordered_map<int,int> &s){↵
↵
↵
if(hv[u]){↵
hld(hv[u],sub,s);↵
dp[u] = dp[hv[u]];↵
for(int i = 0;i<26;i++){↵
int x = b[u]^(1<<i);↵
if(s.find(x)!=s.end())↵
dp[u] = max(dp[u], s[x]-rnk[u]);↵
}↵
if(s.find(b[u])!=s.end())↵
dp[u] = max(dp[u], s[b[u]]-rnk[u]);↵
}↵
↵
s[b[u]] = max(s[b[u]], rnk[u]);↵
sub.pb(u);↵
↵
↵
↵
↵
for(ii p : g[u]){↵
int v = p.f;↵
if(v==hv[u]) continue;↵
↵
vector<int> sub2;↵
unordered_map<int,int> s2;↵
s2.reserve(sz[v]);↵
hld(v, sub2, s2);↵
dp[u] = max(dp[u], dp[v]);↵
↵
for(int x : sub2){↵
int k = b[x];↵
for(int i = 0;i<26;i++){↵
int tmp = k^(1<<i);↵
if(s.find(tmp)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[tmp]-rnk[u]*2);↵
}↵
if(s.find(k)!=s.end()) dp[u] = max(dp[u], rnk[x]+s[k]-rnk[u]*2);↵
↵
}↵
for(int x : sub2){↵
sub.pb(x);↵
s[b[x]] = max(s[b[x]], rnk[x]);↵
}↵
}↵
}↵
↵
↵
int32_t main(){↵
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);↵
↵
// #ifndef ONLINE_JUDGE↵
// freopen("abc.inp","r",stdin);↵
// freopen("abc.out","w",stdout);↵
// #endif↵
↵
cin>>n;↵
for(int i = 2;i<=n;i++){↵
int u; char c;↵
cin>>u>>c;↵
int x = (1<<(c-'a'));↵
g[u].pb(mp(i,x));↵
}↵
↵
↵
rnk[1] = 1;↵
dfs(1);↵
↵
↵
vector<int> sub;↵
unordered_map<int,int> s;↵
↵
s.reserve(n);↵
hld(1, sub, s);↵
for(int i = 1;i<=n;i++) cout<<max(dp[i],0)<<' '; cout<<en;↵
↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
↵
↵
EDIT: Got rid of the ```map```, not sure how to explain it tho. And the solution above would've WAed test 32 because i forgot to make the default value of the map to be ```-INF```↵
↵
Accepted solution: https://codeforces.net/contest/741/submission/287930415↵
