2020-2021:teams:legal_string:jxm2001:树上启发式合并
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:树上启发式合并 [2020/07/26 15:47] jxm2001 |
2020-2021:teams:legal_string:jxm2001:树上启发式合并 [2020/07/28 20:31] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| ===== 算法简介 ===== | ===== 算法简介 ===== | ||
| - | 可离线处理子树相关信息统计的算法，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。 | + | 一种离线处理子树相关信息统计的算法，时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。 |
| ===== 算法思想 ===== | ===== 算法思想 ===== | ||
| 行 9: | 行 9: | ||
| 首先发现对每棵子树进行信息统计时，只需要合并所有儿子节点所在子树信息，最后加上该节点本身信息即可。 | 首先发现对每棵子树进行信息统计时，只需要合并所有儿子节点所在子树信息，最后加上该节点本身信息即可。 | ||
| - | 考虑信息合并的过程，类比并查集的启发式合并，发现把节点数少的子树信息合并到节点数多的子树将得到更优复杂度。 | + | 考虑优化信息合并的过程，类比并查集的启发式合并。 |
| + | |||
| + | 显然把节点数少的子树信息合并到节点数多的子树将得到更优复杂度。 | ||
| 于是考虑保留重儿子子树的统计信息，然后暴力遍历轻儿子子树，合并结果。 | 于是考虑保留重儿子子树的统计信息，然后暴力遍历轻儿子子树，合并结果。 | ||
| 行 132: | 行 134: | ||
| === 题解 === | === 题解 === | ||
| + | |||
| + | 题目难度不高，这里仅给出代码供参考。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 222: | 行 226: | ||
| === 题解 === | === 题解 === | ||
| + | |||
| + | 题目难度不高，这里仅给出代码供参考。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 292: | 行 298: | ||
| _rep(i,1,n) | _rep(i,1,n) | ||
| enter(ans[i]); | enter(ans[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ==== 习题三 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/CF741D|CF741D]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 给定一个以 $1$ 为根的 $n$ 个节点的树，树上每条边代表一个英文小写字母($a\sim v$)。对于每个点，求其子树中的最长回文路径。 | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 显然树上启发式合并不能直接统计路径，想办法把路径转化为点权。 | ||
| + | |||
| + | 考虑状压异或，令每个节点点权为根节点到该节点的路径的字母的异或和。 | ||
| + | |||
| + | 则任意两点间路径构成回文串等价于这两点点权异或为 $0$ 或者恰为 $2$ 的幂次。 | ||
| + | |||
| + | 对每个结点的答案，先考虑经过根节点的路径贡献，可以使用桶记录每个点权出现的最大深度，利用深度可以得到路径长度。 | ||
| + | |||
| + | 对与子树中的路径，可以从子树向上合并答案。 | ||
| + | |||
| + | 时间复杂度 $O(cn\log n)$，空间复杂度 $O(2^c)$，其中 $c$ 为字母种类数。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e5+5,MAXS=22; | ||
| + | struct Edge{ | ||
| + | int to,w,next; | ||
| + | }edge[MAXN]; | ||
| + | int head[MAXN],edge_cnt; | ||
| + | void Insert(int u,int v,int w){ | ||
| + | edge[++edge_cnt]=Edge{v,w,head[u]}; | ||
| + | head[u]=edge_cnt; | ||
| + | } | ||
| + | int c[1<<MAXS],ans[MAXN]; | ||
| + | int d[MAXN],sz[MAXN],w[MAXN],dfs_id[MAXN],node_id[MAXN],dfs_t; | ||
| + | int h_son[MAXN],mson[MAXN]; | ||
| + | void dfs_1(int u){ | ||
| + | sz[u]=1;dfs_id[u]=++dfs_t;node_id[dfs_t]=u;mson[u]=0; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | w[v]=w[u]^edge[i].w; | ||
| + | d[v]=d[u]+1; | ||
| + | dfs_1(v); | ||
| + | sz[u]+=sz[v]; | ||
| + | if(sz[v]>mson[u]){ | ||
| + | h_son[u]=v; | ||
| + | mson[u]=sz[v]; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | int query_node(int u){ | ||
| + | int ans=c[w[u]]+d[u]; | ||
| + | _for(i,0,MAXS){ | ||
| + | if(c[w[u]^(1<<i)]+d[u]>ans) | ||
| + | ans=c[w[u]^(1<<i)]+d[u]; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | void add_node(int u){c[w[u]]=max(c[w[u]],d[u]);} | ||
| + | int add_tree(int u){ | ||
| + | int ans=0; | ||
| + | _for(i,0,sz[u]) | ||
| + | ans=max(ans,query_node(node_id[dfs_id[u]+i])); | ||
| + | _for(i,0,sz[u]) | ||
| + | add_node(node_id[dfs_id[u]+i]); | ||
| + | return ans; | ||
| + | } | ||
| + | void del_node(int u){c[w[u]]=-MAXN;} | ||
| + | void del_tree(int u){ | ||
| + | _for(i,0,sz[u]) | ||
| + | del_node(node_id[dfs_id[u]+i]); | ||
| + | } | ||
| + | void dfs_2(int u,bool del){ | ||
| + | ans[u]=d[u]*2; | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==h_son[u])continue; | ||
| + | dfs_2(v,true); | ||
| + | } | ||
| + | if(h_son[u])dfs_2(h_son[u],false); | ||
| + | ans[u]=max(ans[u],query_node(u)); | ||
| + | c[w[u]]=max(c[w[u]],d[u]); | ||
| + | for(int i=head[u];i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(v==h_son[u])continue; | ||
| + | ans[u]=max(ans[u],add_tree(v)); | ||
| + | } | ||
| + | ans[u]-=d[u]*2; | ||
| + | for(int i=head[u];i;i=edge[i].next) | ||
| + | ans[u]=max(ans[u],ans[edge[i].to]); | ||
| + | if(del)del_tree(u); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),root=1,f;char cc; | ||
| + | _for(i,0,1<<MAXS) | ||
| + | c[i]=-MAXN; | ||
| + | _rep(i,2,n){ | ||
| + | f=read_int(); | ||
| + | cc=get_char(); | ||
| + | Insert(f,i,1<<(cc-'a')); | ||
| + | } | ||
| + | w[root]=0;d[root]=0; | ||
| + | dfs_1(root); | ||
| + | dfs_2(root,false); | ||
| + | _rep(i,1,n) | ||
| + | space(ans[i]); | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/树上启发式合并.1595749671.txt.gz · 最后更改: 2020/07/26 15:47 由 jxm2001
