CodeChef Tree Palindromes
2024-09-03 14:24:14
Tree Palindromes
Given a tree rooted at node 1 with N nodes, each is assigned a lower case latin character. Print the sum of length of longest palindrome substring from string generated by simple path from root to all other nodes i.e root to some other node (say x) will represent a string, find its lps length and add it to answer for all such nodes x. Then print final answer.
1 ≤ N ≤ 105
题解
翁文涛《回文树及其应用》。
回文树也可以有类似AC自动机的不全转移,不过这个补全是间接性的。
\(t=even\) 的时候要特殊处理。考虑实际意义(或者get_fail
过程)可知 \(quick_{even}[c]=odd\)。
有了这个Trie上就好做了。
本题字符集较小,在插入的时候,没有必要将失配转移可持久化,直接开一个数组记录即可。时间复杂度 \(O(n\Sigma)\)。
CO int N=100000+10;
vector<int> to[N];
namespace PAM{
int str[N],n;
int tot;
int ch[N][26],trans[N][26],fa[N],len[N];
IN void init(){
memset(str,-1,sizeof str);
tot=1;
fa[0]=fa[1]=1;
len[0]=0,len[1]=-1;
fill(trans[0],trans[0]+26,1);
}
int extend(int p,int c){
if(str[n-len[p]-1]!=str[n]) p=trans[p][c];
if(!ch[p][c]){
int cur=++tot;
len[cur]=len[p]+2;
fa[cur]=ch[trans[p][c]][c];
ch[p][c]=cur;
copy(trans[fa[cur]],trans[fa[cur]]+26,trans[cur]);
trans[cur][str[n-len[fa[cur]]]]=fa[cur];
}
return ch[p][c];
}
}
char tree[N];
int last[N],res[N];
LL ans;
void dfs(int x,int fa){
PAM::str[++PAM::n]=tree[x]-'a';
last[x]=PAM::extend(last[fa],tree[x]-'a');
res[x]=max(res[fa],PAM::len[last[x]]);
ans+=res[x];
for(int i=0;i<(int)to[x].size();++i)
if(to[x][i]!=fa) dfs(to[x][i],x);
--PAM::n;
}
int main(){
int n=read<int>();
scanf("%s",tree+1);
for(int i=1;i<n;++i){
int u=read<int>(),v=read<int>();
to[u].push_back(v),to[v].push_back(u);
}
PAM::init();
dfs(1,0);
printf("%lld\n",ans);
return 0;
}
最新文章
- linux 命令 之判断表达式
- JavaScriptPolyfillShim 在JavaScript中Shim和Polyfill有什么区别?
- 关于 矩阵在ACM中的应用
- 模拟赛1101d2
- ACM 疯牛
- 关于TouchEvent里面的touches,targetTouches,changedTouches的解释
- Codeforces Round #336 (Div. 2) C. Chain Reaction set维护dp
- 1031: [JSOI2007]字符加密Cipher - BZOJ
- 算法专题训练 搜索a-T3 Ni骑士(ni)
- information_schema.partitions 学习
- objective-c 关键字和概念
- C#基础面试
- 动态字符串 Stringbuilder类
- JAVA之File类创建对象构造函数传参数需要注意的几点
- Elasticsearch java api 常用查询方法QueryBuilder构造举例
- python接口测试-认识POST请求
- python模块中sys.argv[]使用
- vm centos7中用NAT模式配置上网
- leftJoin鏈錶查詢
- Objective-C:动态绑定