【JZOJ5363】【NOIP2017提高A组模拟9.14】生命之树 Trie+启发式合并
题面 45 在比赛中，我只想到了45分的暴力。对于一个树中点对，相当于在他们的LCA及其祖先加上这个点对的贡献。那么这个可以用dfs序+树状数组来维护。 100 想法 我想到了可能要用trie树来维护这个字符串的公共前缀。然后这就面临了两个很严重的问题。1.我对于每个子树都要建一个trie，所以这...
jzoj5363【NOIP2017提高A组模拟9.14】生命之树 trie+启发式合并
题意：有一颗树，每个点有一个权值和一个字符串，要求计算出以每个点的子树的贡献，贡献的定义是两个点权值的xor*两个点字符串的lcp。n<=1e5其实这题我第一眼就想到trie，但是我trie基本上没做过多少题，不会xor统计的那种科技（这个太基础了吧喂），然后就异想天开用了个SA，结果爆炸，调...
【JZOJ5363】【NOIP2017提高A组模拟9.14】生命之树 Trie+启发式合并
题面 45 在比赛中，我只想到了45分的暴力。对于一个树中点对，相当于在他们的LCA及其祖先加上这个点对的贡献。那么这个可以用dfs序+树状数组来维护。 100 想法 我想到了可能要用trie树来维护这个字符串的公共前缀。然后这就面临了两个很严重的问题。1.我对于每个子树都要建一个trie，所以这...
hdu5790 Prefix（2016多校第五场1009）trie+主席树
如果不强制在线可以莫队乱搞，但是现在我们就想怎么把trie可持久化，其实我们只要记录一个点的存在范围即可，即从小到大建立主席树，对于每个点我们在主席树里面记录最右边的位置，也就是对于r记录的是最大的l，那就好办了，只求求和即可。 #include<cstdio>#include<...
bzoj3439 trie+可持久化线段树
挺好想的trie建树后，按dfn序建可持久化注意：计数变量多的题目一定要注意检查会不会用的时候搞混了#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#in...