做羞羞的事情网站,做网站用什么语言数据库,用php做高中数学题库网站,大学 英文网站建设正题 题目大意 nnn个点的一棵树#xff0c;每个节点有一个值valvalval和一个字符串SSS。对于每个点求∑x∈decp∑y∈decp(xy)(valxxorvaly)∗∣LCP(Sx,Sy)∣\sum_{x\in dec_p}\sum_{y\in dec_p(xy)}(val_x\ xor\ val_y)*|LCP(S_x,S_y)|x∈decp∑y∈decp(xy)…正题 题目大意
nnn个点的一棵树每个节点有一个值valvalval和一个字符串SSS。对于每个点求∑x∈decp∑y∈decp(xy)(valxxorvaly)∗∣LCP(Sx,Sy)∣\sum_{x\in dec_p}\sum_{y\in dec_p(xy)}(val_x\ xor\ val_y)*|LCP(S_x,S_y)|x∈decp∑y∈decp(xy)∑(valx xor valy)∗∣LCP(Sx,Sy)∣ decxdec_xdecx表示xxx的子树。 解题思路
我们可以通过建立一棵TrieTrieTrie来查询一个字符串和一堆字符串的LCPLCPLCP和。那么我们发现这样每个子树的运输次数是该子树的字符串长度和。
所以我们可以根据字符串长度和来进行启发式合并然后按位用TrieTrieTrie统计答案即可。
时间复杂度O(nlognlogai)O(n\log n\log a_i)O(nlognlogai) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e510;
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(){cnt1;memset(t[1],0,sizeof(t[1]));return;}void Insert(ll w){ll x1;for(ll i1;il[w];i){ll zs[pos[w]i];if(!t[x][z]){t[x][z]cnt;val[cnt]0;memset(t[cnt],0,sizeof(t[cnt]));}xt[x][z];val[x];}return;}ll Ask(ll w){ll x1,ans0;for(ll i1;il[w];i){ll zs[pos[w]i];if(!t[x][z])return ans;xt[x][z];ansval[x];}return ans;}
}T1,T0;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){siz[x]l[x]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)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 ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;anscalcA(y,x);}return ans;
}
void calcI(ll x,ll fa){(val[x]W)?T1.Insert(x):T0.Insert(x);for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;calcI(y,x);}return;
}
void solve(ll x,ll fa,ll top){ans[x]0;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||yson[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 ils[x];i;ia[i].next)if(a[i].to!faa[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(xtop)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 i1;in;i)scanf(%lld,val[i]);for(ll i1;in;i){scanf(%s,st1);l[i]strlen(st1);for(ll j1;jl[i];j)s[pos[i]j]st[j]-a;pos[i1]pos[i]l[i];}for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}T1.Clear();T0.Clear(); dfs(1,0);for(W1;W1e5;W1)solve(1,1,1);for(ll i1;in;i)printf(%lld\n,out[i]);
}
