正題

---

題目大意

$n$個(gè)點(diǎn)的一棵樹(shù)，每個(gè)節(jié)點(diǎn)有一個(gè)值$val$和一個(gè)字符串$S$。對(duì)于每個(gè)點(diǎn)求$$\sum _{x\in de{c}_p}\sum _{y\in de{c}_p(x<y)}(va{l}_{x}xorva{l}_y)?|LCP(S_x,S_y)|$$
$de{c}_x$表示$x$的子樹(shù)。

---

解題思路

我們可以通過(guò)建立一棵$Trie$來(lái)查詢一個(gè)字符串和一堆字符串的$LCP$和。那么我們發(fā)現(xiàn)這樣每個(gè)子樹(shù)的運(yùn)輸次數(shù)是該子樹(shù)的字符串長(zhǎng)度和。

所以我們可以根據(jù)字符串長(zhǎng)度和來(lái)進(jìn)行啟發(fā)式合并，然后按位用$Trie$統(tǒng)計(jì)答案即可。

時(shí)間復(fù)雜度$O(n\log n\log a_i)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e5+10; struct node{ll to,next; }a[N*2]; ll n,tot,W,val[N],ls[N],l[N],s[N],pos[N]; ll siz[N],son[N],ans[N],out[N]; char st[N]; struct Trie{ll cnt,t[N][26],val[N];void Clear(){cnt=1;memset(t[1],0,sizeof(t[1]));return;}void Insert(ll w){ll x=1;for(ll i=1;i<=l[w];i++){ll z=s[pos[w]+i];if(!t[x][z]){t[x][z]=++cnt;val[cnt]=0;memset(t[cnt],0,sizeof(t[cnt]));}x=t[x][z];val[x]++;}return;}ll Ask(ll w){ll x=1,ans=0;for(ll i=1;i<=l[w];i++){ll z=s[pos[w]+i];if(!t[x][z])return ans;x=t[x][z];ans+=val[x];}return ans;} }T1,T0; void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(ll x,ll fa){siz[x]=l[x]+1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dfs(y,x);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y;}return; } ll calcA(ll x,ll fa){ll ans=(val[x]&W)?T0.Ask(x):T1.Ask(x);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;ans+=calcA(y,x);}return ans; } void calcI(ll x,ll fa){(val[x]&W)?T1.Insert(x):T0.Insert(x);for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;calcI(y,x);}return; } void solve(ll x,ll fa,ll top){ans[x]=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa||y==son[x])continue;solve(y,x,y);ans[x]+=ans[y];}if(son[x])solve(son[x],x,top);ans[x]+=ans[son[x]];for(ll i=ls[x];i;i=a[i].next)if(a[i].to!=fa&&a[i].to!=son[x])ans[x]+=calcA(a[i].to,x),calcI(a[i].to,x);ans[x]+=(val[x]&W)?T0.Ask(x):T1.Ask(x);out[x]+=ans[x]*W;if(x==top)T0.Clear(),T1.Clear();else (val[x]&W)?T1.Insert(x):T0.Insert(x);return; } int main() {freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&val[i]);for(ll i=1;i<=n;i++){scanf("%s",st+1);l[i]=strlen(st+1);for(ll j=1;j<=l[i];j++)s[pos[i]+j]=st[j]-'a';pos[i+1]=pos[i]+l[i];}for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}T1.Clear();T0.Clear(); dfs(1,0);for(W=1;W<=1e5;W<<=1)solve(1,1,1);for(ll i=1;i<=n;i++)printf("%lld\n",out[i]); }

總結(jié)

以上是生活随笔為你收集整理的jzoj5363-[NOIP2017提高A组模拟9.14]生命之树【启发式合并,Trie】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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