[树上启发式合并 && 哈希] Codeforces 741D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

xiaoxiao2021-02-28  10

日常VP翻车

学一发树上启发式合并,%%%gjghfd 树上启发式合并可以截这里

每次递归做轻儿子,做完后清空轻儿子信息(注意是做完一个轻儿子后发现清空这个),然后做重儿子,再dfs所有轻儿子并跟新当前点的答案,然后把轻儿子信息加进去……

说起来很绕,其实挺好理解的… 每个节点的哈希值就是它到根路径哪些字符出现奇数次,记录就是记录每个哈希值的深度的最大值,然后类似求路径长度搞一搞就好了

#include <cstdio> #include <iostream> #include <algorithm> #include <tr1/unordered_map> #include <vector> #define fi first #define se second using namespace std; using namespace tr1; typedef pair<int,int> ii; const int N=500010; int n,ans[N],a[N],hs[N],dpt[N],son[N],sz[N],f[1<<23]; vector<ii> s[N]; inline void fix(int &x,int y){ if(x<y) x=y; } void dfs(int x){ sz[x]=1; for(ii i : s[x]){ hs[i.fi]=hs[x]^(1<<i.se); dpt[i.fi]=dpt[x]+1; dfs(i.fi); sz[x]+=sz[i.fi]; if(sz[i.fi]>sz[son[x]]) son[x]=i.fi; } } void del(int x){ f[hs[x]]=0; for(ii i : s[x]) del(i.fi); } void add(int x){ for(ii i : s[x]) add(i.fi); fix(f[hs[x]],dpt[x]); } void check(int x,int u){ if(f[hs[x]]) fix(ans[u],dpt[x]+f[hs[x]]-2*dpt[u]); for(int i=0;i<22;i++) if(f[hs[x]^(1<<i)]) fix(ans[u],dpt[x]+f[hs[x]^(1<<i)]-2*dpt[u]); for(ii i : s[x]) check(i.fi,u); } void solve(int x){ for(ii i : s[x]){ int u=i.fi; if(u!=son[x]) solve(u),del(u); } if(son[x]) solve(son[x]); for(ii i : s[x]){ int u=i.fi; fix(ans[x],ans[u]); if(u!=son[x]) check(u,x),add(u); } fix(ans[x],f[hs[x]]-dpt[x]); for(int j=0;j<22;j++) fix(ans[x],f[hs[x]^(1<<j)]-dpt[x]); fix(f[hs[x]],dpt[x]); } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d",&n); for(int i=2;i<=n;i++){ int p; char c; scanf("%d %c",&p,&c); s[p].push_back(ii(i,c-'a')); } dfs(1); solve(1); for(int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1100329.html

最新回复(0)