【日常小测】最长公共前缀

题目大意

给定一棵以$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;
}

【BZOJ 3926】[ZJOI2015] 诸神眷顾的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3926
神犇题解:http://wjmzbmr.com/archives/zjoi-2015-day-1题解/

解题报告

陈老师的语文真刺激!
把叶节点最多只有20个这个条件埋得那么深 QwQ
一开始以为那个条件意思是度数不超过20,于是想边分治,后来都想到”万径人踪灭”去了……

考虑树上每一条路径,至少存在一个叶子结点,使得将该叶子结点作为根后,这条路径上的结点深度递减
于是对于每一个叶节点都DFS一遍,然后建广义后缀自动机
广义自动机的话,直接看这份代码就好吧!
或者想全面学习的话,可以看这里:传送门

另外,这题据陈老师说,后缀数组也可以做
但我不会啊,跪求神犇带 _(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = 2000000;
const int C = 10;

int n,c,col[N],head[N],to[N],nxt[N],in[N];

class Suffix_Automaton{
	int ch[M][C],pre[M],len[M],cnt;
	public:
		inline int insert(int last, int t) {
			int w = ++cnt; len[w] = len[last] + 1; pre[0] = -1;
			for (;~last&&!ch[last][t];last=pre[last]) ch[last][t] = w;
			if (~last) {
				if (len[ch[last][t]] == len[last] + 1) {
					pre[w] = ch[last][t];
				} else {
					int nw = ++cnt, tmp = ch[last][t];
					len[nw] = len[last] + 1; 
					pre[nw] = pre[tmp]; pre[tmp] = pre[w] = nw; 
					memcpy(ch[nw],ch[tmp],sizeof(ch[nw]));
					for (;~last&&ch[last][t]==tmp;last=pre[last]) ch[last][t] = nw;
				}
			} return w;
		} 
		inline LL solve() {
			LL ret = 0;
			for (int i=1;i<=cnt;i++)
				ret += len[i] - len[pre[i]];
			return ret; 
		}
}SAM;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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) {
	static int E = 1; in[u]++; in[v]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f, int s) {
	int rt = SAM.insert(s, col[w]);
	for (int i=head[w];i;i=nxt[i]) 
		if (to[i] != f) DFS(to[i], w, rt);
}

int main() {
	n = read(); c = read();
	for (int i=1;i<=n;i++) col[i] = read();
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	for (int i=1;i<=n;i++) if (in[i] == 1) DFS(i, i, 0);
	printf("%lld\n",SAM.solve());
	return 0;
}