[JZOJ5363]生命之樹

題目大意

給定一棵 n 個節點的樹，1号節點為根每個節點上面有一個由小寫字母組成的字元串 Si 和一個權值 vali ，兩個字元串 Si,Sj 組合起來的收益為 LCP(Si,Sj) 。

定義 decu 為 u 子樹内所有的點，那麼以u為根的子樹的總收益為

ansu=∑i∈decu∑j∈decu,i<j(vali xor valj)×LCP(Si,Sj)

對每一節點輸出其子樹的總收益。

2≤n≤105,0≤vali≤105,1≤u,v≤n,∑|Si|≤5×105

題目分析

看到異或運算直接拆位。

考慮維護一個子樹的 Trie ，統計答案的話可以每一個節點開一個 logval 的數組記錄某一位是 0/1 的節點由多少個，然後枚舉 Trie 上節點。

然後我們直接用線段樹合并的方法合并 Trie 同時更新答案就好了。

時間複雜度 O(∑|Si|lognlogval) 。

代碼實作

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long LL;

int read()
{
    int x=,f=;
    char ch=getchar();
    while (!isdigit(ch)) f=ch=='-'?-:f,ch=getchar();
    while (isdigit(ch)) x=x*+ch-'0',ch=getchar();
    return x*f;
}

int buf[];

void write(LL x)
{
    if (x<) putchar('-'),x=-x;
    for (;x;x/=) buf[++buf[]]=x%;
    if (!buf[]) buf[++buf[]]=;
    for (;buf[];putchar('0'+buf[buf[]--]));
}

const int N=;
const int E=N<<;
const int L=;
const int LGN=;
const int S=L+N;
const int C=;

int val[N],last[N];
int tov[E],nxt_[E];
char str[L];
LL ans[N];
int n,tot;

int cnt[S][LGN][];
int nxt[S][C];
int root[N];
int tots;

int newnode(int val)
{
    ++tots;
    for (int i=;i<LGN;++i,val>>=) ++cnt[tots][i][val&];
    return tots;
}

void ins(int id,int val)
{
    int rt=root[id]=newnode(),len=strlen(str);
    for (int i=;i<len;++i) nxt[rt][str[i]-'a']=newnode(val),rt=nxt[rt][str[i]-'a'];
}

int merge(int x,int y,LL &ret)
{
    if (!x||!y) return x^y;
    for (int i=;i<LGN;++i)
    {
        ret+=(l*cnt[x][i][]*cnt[y][i][]+l*cnt[x][i][]*cnt[y][i][])*(<<i);
        cnt[x][i][]+=cnt[y][i][],cnt[x][i][]+=cnt[y][i][];
    }
    for (int c=;c<C;++c) nxt[x][c]=merge(nxt[x][c],nxt[y][c],ret);
    return x;
}

void insert(int x,int y){tov[++tot]=y,nxt_[tot]=last[x],last[x]=tot;}

void dfs(int x,int fa=)
{
    ans[x]=;
    for (int i=last[x],y;i;i=nxt_[i])
        if ((y=tov[i])!=fa) dfs(y,x),ans[x]+=ans[y],root[x]=merge(root[x],root[y],ans[x]);
}

int main()
{
    freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
    n=read();
    for (int i=;i<=n;++i) val[i]=read();
    for (int i=;i<=n;++i) scanf("%s",str),ins(i,val[i]);
    for (int i=,x,y;i<n;++i) x=read(),y=read(),insert(x,y),insert(y,x);
    dfs();
    for (int i=;i<=n;++i) write(ans[i]),putchar('\n');
    fclose(stdin),fclose(stdout);
    return ;
}