題目鏈接：點(diǎn)擊查看

題目分析：初始時(shí)給出一棵以點(diǎn) $0$ 為根節(jié)點(diǎn)的字典樹，設(shè) $ar{r}_i$ 為從根節(jié)點(diǎn)出發(fā)到達(dá)點(diǎn) $i$ 的字符串，需要回答對(duì)于每個(gè) $i\in [1,n]$ 時(shí)的 ${\sum }_{k=1}^{n}f(ar{r}_i,ar{r}_k)$，其中 $f(s,t)$ 代表的是字符串 $s$ 在字符串 $t$ 中出現(xiàn)的次數(shù)

題目分析：
先附上官方題解：

本題難點(diǎn)及解決方法：

字符集過大（可持久化數(shù)組優(yōu)化getfail）

如何統(tǒng)計(jì)答案：一個(gè)串在另一個(gè)串中出現(xiàn)，只可能是兩種情況：

作為前綴：直接統(tǒng)計(jì)字典樹中某個(gè)節(jié)點(diǎn)的子樹大小即可

作為中間的位置：所有能夠沿著 $fail$ 邊跳到當(dāng)前節(jié)點(diǎn)的點(diǎn)的總和，建出 $fail$ 樹然后 $dp$ 一下即可

需要注意的一個(gè)小坑點(diǎn)就是，因?yàn)樽值錁渖系淖址傞L(zhǎng)最大可能是 $O(n^2)$ 級(jí)別的，所以答案可能會(huì)爆 $int$，記得開 $longlong$

時(shí)間復(fù)雜度：$O(nlogn)$

代碼：

// Problem: Elo mountains // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/17148/G // Memory Limit: 1048576 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; const int M=1e5; vector<pair<int,int>>edge[N];//原樹 vector<int>node[N];//fail樹 unordered_map<int,int>trans[N];//原樹的字典樹 struct Node {int l,r,val; }tree[N*20];//可持久化數(shù)組 int trie[N],fail[N],tot; LL dp[N],sz[N]; int newnode() {tot++;tree[tot].l=tree[tot].r=tree[tot].val=0;return tot; } void add(int &k,int pos,int val,int l,int r) {int nk=newnode();tree[nk]=tree[k];k=nk;if(l==r) {tree[k].val+=val;return;}int mid=(l+r)>>1;if(pos<=mid) {add(tree[k].l,pos,val,l,mid);} else {add(tree[k].r,pos,val,mid+1,r);} } int ask(int k,int pos,int l,int r) {if(l==r) {return tree[k].val;}int mid=(l+r)>>1;if(pos<=mid) {return ask(tree[k].l,pos,l,mid);} else {return ask(tree[k].r,pos,mid+1,r);} } void getfail() {queue<int>q;for(auto it:trans[0]) {int u=0,v=it.second,to=it.first;add(trie[u],to,v,1,M);fail[v]=u;q.push(v);}while(q.size()) {int u=q.front();q.pop();trie[u]=trie[fail[u]];for(auto it:trans[u]) {int v=it.second,to=it.first;int delta=v-ask(trie[u],to,1,M);add(trie[u],to,delta,1,M);fail[v]=ask(trie[fail[u]],to,1,M);q.push(v);}} } void buildfail(int n) {for(int i=1;i<=n;i++) {dp[fail[i]]+=sz[i];node[fail[i]].push_back(i);} } void dfs1(int u,int fa) {sz[u]=1;for(auto it:edge[u]) {int v=it.first,to=it.second;if(v==fa) {continue;}trans[u][to]=v;dfs1(v,u);sz[u]+=sz[v];} } void dfs2(int u) {for(auto v:node[u]) {dfs2(v);dp[u]+=dp[v];} } void init() {tot=-1;newnode(); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n;read(n);for(int i=1;i<=n;i++) {int u,v,w;read(u),read(v),read(w);edge[u].push_back({v,w});edge[v].push_back({u,w});}dfs1(0,-1);//建字典樹getfail();//得到fail邊buildfail(n);//建fail樹dfs2(0);//fail樹上dpfor(int i=1;i<=n;i++) {printf("%lld\n",dp[i]+sz[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客 - Elo mountains(AC自动机+可持久化数组优化)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。