题目大意
给定一棵以$1$号点为根、大小为$n$的有根树($n \le 10^5$),每一条边上有一个小写英文字母
给定$m$个询问,第$i$个询问包含一个长度为$t_i$的点集(元素可重,$\sum{t_i} \le 2 \cdot 10^5$),询问$\sum\limits_{a=1}^{t_i}{\sum\limits_{b=a+1}^{t_i}{lcp(a,b)}}$
定义$s_a$为从a出发走向根,将边上的字符按顺序写下来构成的字符串
定义$lcp(a,b)$为$s_a$与$s_b$的最长公共前缀
下面举一个栗子
若树长成这样:
那么$s_5=cb,s_4=cbb$
更进一步,若某次询问的点集为$\{4,5\}$那么答案为$2$
解题报告
看到这种树上的字符串,我能想到AC自动机,或者广义后缀自动机
想了想AC自动机做不了,那就广义后缀自动机来做咯!
考虑后缀自动机上的Fail树
一个点的祖先实际上是这个点代表的字符串的后缀
那么题目中的$lcp(a,b)$就变成了$lca(a,b)$
于是对于每一次询问,我们建一个虚树出来
然后在虚树上DFS一次,统计一下答案就好啦!
另外,这题用后缀数组也可以做!
听武爷讲一讲,大概就是先把Trie树建出来
同时记录下每一次倍增的$Rank$数组(波兰表……)
然后就正常倍增,写法已经和罗穗骞的后缀数组的实现很不同了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int M = N << 1; int n,m,E,head[N],nxt[M],to[M],col[M],pos[N],id[N]; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void Add_Edge(int u, int v, int c = 0) { to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c; to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c; } class Suffix_Automaton{ int cnt=1,ch[N][26],fail[N],vis[N],dep[N],sum[N]; int tot,arr[N],que[N],len[N],fa[N][20],_hash[N]; vector<int> G[N]; LL ans_tmp; public: inline int insert(int t, int cc) { if (ch[t][cc] && len[ch[t][cc]] == len[t] + 1) return ch[t][cc]; int tail = ++cnt; len[tail] = len[t] + 1; while (!ch[t][cc] && t) ch[t][cc] = tail, t=fail[t]; if (!t) fail[tail] = 1; else { if (len[ch[t][cc]] == len[t] + 1) fail[tail] = ch[t][cc]; else { int nw = ++cnt, w = ch[t][cc]; len[nw] = len[t]+1; memcpy(ch[nw], ch[w], sizeof(ch[nw])); fail[nw] = fail[w]; fail[w] = fail[tail] = nw; for (;ch[t][cc]==w;t=fail[t]) ch[t][cc] = nw; } } return tail; } inline void Build_Fail_Tree() { memset(head,0,sizeof(head)); E = 0; for (int i=2;i<=cnt;i++) Add_Edge(fail[i], i); dfs(1, 1); for (int j=1;j<20;j++) { for (int i=1;i<=cnt;i++) { fa[i][j] = fa[fa[i][j-1]][j-1]; } } } inline LL solve(int nn) { for (int i=1;i<=nn;i++) arr[i] = pos[read()]; sort(arr+1, arr+1+nn, [](const int &a, const int &b) {return id[a] < id[b];}); for (int i=1;i<=nn;i++) _hash[i] = arr[i]; int mm = nn; nn = unique(arr+1, arr+1+nn) - arr - 1; for (int i=1;i<=nn;i++) sum[i] = 0; for (int i=1,j=1;i<=mm;i++) { while (arr[j] != _hash[i]) j++; sum[j]++; } que[tot=1] = 1; int MX = 1; for (int i=1,lca;i<=nn;i++) { vis[arr[i]] = sum[i]; lca = LCA(que[tot], arr[i]); while (dep[que[tot]] > dep[lca]) { if (dep[que[tot-1]] >= dep[lca]) G[que[tot-1]].push_back(que[tot]); else G[lca].push_back(que[tot]); --tot; } if (que[tot] != lca) que[++tot] = lca; if (arr[i] != que[tot]) que[++tot] = arr[i]; MX = max(MX, tot); } while (tot > 1) G[que[tot-1]].push_back(que[tot]), --tot; ans_tmp = 0; Get_Ans(1); return ans_tmp; } private: void dfs(int w, int f) { static int id_count = 0; id[w] = ++id_count; fa[w][0] = f; dep[w] = dep[f] + 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { dfs(to[i], w); } } } int Get_Ans(int w) { int ret = vis[w]; if (w > 1) ans_tmp += vis[w] * (vis[w] - 1ll) / 2 * len[w]; for (int i=G[w].size()-1,tmp;~i;i--) { tmp = Get_Ans(G[w][i]); ans_tmp += (LL)tmp * ret * len[w]; ret += tmp; } vis[w] = 0; G[w].clear(); return ret; } inline int LCA(int a, int b) { if (dep[a] < dep[b]) swap(a, b); for (int i=19;~i;i--) if (dep[fa[a][i]] >= dep[b]) a = fa[a][i]; if (a == b) return a; for (int i=19;~i;i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i]; return fa[a][0]; } }SAM; void DFS(int w, int f, int t) { pos[w] = t; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { int nt = SAM.insert(t, col[i]); DFS(to[i], w, nt); } } } int main() { n = read(); char pat[10]; for (int i=1,u,v;i<n;i++) { u = read(); v = read(); scanf("%s",pat+1); Add_Edge(u, v, pat[1] - 'a'); } DFS(1, 1, 1); SAM.Build_Fail_Tree(); for (int i=read();i;i--) printf("%lld\n",SAM.solve(read())); return 0; }