【题目】D. Acyclic Organic Compounds
【题意】给定一棵带点权树，每个点有一个字符，定义一个结点的字符串数为往下延伸能得到的不重复字符串数，求min（点权+字符串数），n<=300000，time=3s。
【算法】trie合并||hash+线段树合并||dsu on tree
【题解】维护每个节点的Trie，那么每个节点的不重复字符串数是Trie的节点数。
每个节点Tire的根设为这个节点的字符（不是空字符）。
这样Trie的合并就很方便了，merge(a,b)表示将b并入a下一层，假设b的根字符为c：
如果存在trans(a,c)，那么累计重叠一个节点，继续合并。
否则加入trans(a,c)=b，退出。
这样能统计出总共重叠多少个节点，merge结束后在size(a)中减去。
合并的复杂度分析和线段树合并分析相同，复杂度为$O(26*n)$。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> using namespace std; int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } const int maxn=300010; int n,tot,ans=0,ansnum=0,num[maxn],first[maxn],ch[maxn][30],sz[maxn]; char s[maxn]; struct edge{int v,from;}e[maxn*2]; void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;} int merge(int a,int b){ int x=s[b]-'a',sum; if(ch[a][x]){ sum=1; for(int i=0;i<26;i++)if(ch[b][i])sum+=merge(ch[a][x],ch[b][i]); } else{ sum=0; ch[a][x]=b; } return sum; } void dfs(int x,int fa){ sz[x]=1; for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){ dfs(e[i].v,x); sz[x]+=sz[e[i].v]; sz[x]-=merge(x,e[i].v); } if(ans<num[x]+sz[x]){ ans=num[x]+sz[x]; ansnum=1; }else if(ans==num[x]+sz[x])ansnum++; } int main(){ n=read(); for(int i=1;i<=n;i++)num[i]=read(); scanf("%s",s+1); for(int i=1;i<n;i++){ int u=read(),v=read(); insert(u,v);insert(v,u); } dfs(1,0); printf("%d %d",ans,ansnum); return 0; }
hash+线段树合并：主要问题在于每次都会增加一个字符，取模后就破坏了原有顺序。
解决方法是，每个点记录从根到它的字符串的哈希值，两个遇到一起会消去的字符串一定从根开始就相同。
然后将这些哈希值离散化后线段树合并即可，复杂度O(n log n)。
平衡树+启发式合并，复杂度O(n log2n)。
注意：CodeForces卡自然溢出，可以取模1e18+7效果就和自然溢出差不多了。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define ul unsigned long long using namespace std; int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } const int maxn=300010,base=23333333; int n,tot,cnt,first[maxn],root[maxn],num[maxn],ans=0,ansnum=0; ul g[maxn],h[maxn],MOD=1000000000000000009; char s[maxn]; struct tree{int l,r,sum;}t[maxn*50]; struct edge{int v,from;}e[maxn*2]; void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;} void dfs(int x,int fa,ul num){ g[x]=h[x]=(1ull*num*base+s[x]+233)%MOD; for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){ dfs(e[i].v,x,h[x]); } } void build(int l,int r,int &k,int x){ if(!k)k=++cnt;t[k].sum=1; if(l==r)return; int mid=(l+r)>>1; if(x<=mid)build(l,mid,t[k].l,x); else build(mid+1,r,t[k].r,x); } int merge(int l,int r,int a,int b){ if(!a||!b)return a^b; if(l==r){t[a].sum=1;return a;} int mid=(l+r)>>1; t[a].l=merge(l,mid,t[a].l,t[b].l); t[a].r=merge(mid+1,r,t[a].r,t[b].r); t[a].sum=t[t[a].l].sum+t[t[a].r].sum; return a; } void ask(int x,int fa){ for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){ ask(e[i].v,x); root[x]=merge(1,tot,root[x],root[e[i].v]); } if(num[x]+t[root[x]].sum>ans){ ans=num[x]+t[root[x]].sum; ansnum=1; } else if(num[x]+t[root[x]].sum==ans)ansnum++; } int main(){ n=read(); for(int i=1;i<=n;i++)num[i]=read(); scanf("%s",s+1); for(int i=1;i<n;i++){ int u=read(),v=read(); insert(u,v);insert(v,u); } dfs(1,0,0); sort(g+1,g+n+1); tot=unique(g+1,g+n+1)-g-1; for(int i=1;i<=n;i++)h[i]=lower_bound(g+1,g+tot+1,h[i])-g; for(int i=1;i<=n;i++)build(1,tot,root[i],h[i]); ask(1,0); printf("%d %d",ans,ansnum); return 0; }
dsu on tree：见官方题解。