trie合并的裸题...因为最多只有n个点，所以最多合并n次，复杂度$O(N*26)$。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int maxn=500010, inf=1e9; struct poi{int too, pre;}e[maxn<<1]; struct tjm{int nxt[26], size;}tree[maxn]; int n, x, y, ans, cnt, tot; int last[maxn], c[maxn]; char s[maxn]; inline void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;} void merge(int &x, int y) { if(!x || !y) {x+=y; return;} tree[x].size=1; for(int i=0;i<26;i++) merge(tree[x].nxt[i], tree[y].nxt[i]), tree[x].size+=tree[tree[x].nxt[i]].size; } void dfs(int x, int fa) { tree[x].size=1; for(int i=last[x], too;i;i=e[i].pre) if((too=e[i].too)!=fa) { dfs(too, x); int tmp=tree[tree[x].nxt[s[e[i].too]-'a']].size; merge(tree[x].nxt[s[e[i].too]-'a'], e[i].too); tree[x].size+=tree[tree[x].nxt[s[e[i].too]-'a']].size-tmp; } if(tree[x].size+c[x]>ans) ans=tree[x].size+c[x], cnt=1; else if(tree[x].size+c[x]==ans) cnt++; } int main() { read(n); for(int i=1;i<=n;i++) read(c[i]); scanf("%s", s+1); for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x); dfs(1, 0); printf("%d %d", ans, cnt); }
当然还可以直接上哈希+平衡树+启发式合并，用set自带去重就好了，复杂度$O(Nlog^2N)$。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<set> #define ll long long using namespace std; const int maxn=500010, inf=1e9; const ll mod=233333333333333333; typedef set<ll>::iterator ddq; struct poi{int too, pre;}e[maxn<<1]; int n, x, y, tot, ans, ansnum; int last[maxn], c[maxn], root[maxn]; ll hs[maxn]; char ch[maxn]; set<ll>s[maxn]; inline void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;} inline int merge(int x, int y) { if(s[x].size()<s[y].size()) swap(x, y); for(ddq ity=s[y].begin();ity!=s[y].end();ity++) s[x].insert(*ity); s[y].clear(); return x; } void dfs(int x, int fa) { hs[x]=(hs[fa]*27+ch[x]-'a'+1)%mod; s[x].insert(hs[x]); root[x]=x; for(int i=last[x], too;i;i=e[i].pre) if((too=e[i].too)!=fa) { dfs(too, x); root[x]=merge(root[x], root[too]); } int size=s[root[x]].size(); if(size+c[x]>ans) ans=size+c[x], ansnum=1; else if(size+c[x]==ans) ansnum++; } int main() { read(n); for(int i=1;i<=n;i++) read(c[i]); scanf("%s", ch+1); for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x); dfs(1, 0); printf("%d %d", ans, ansnum); }
当然还可以hash之后用dsu on tree，复杂度$O(NlogN)$。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010, inf=1e9; const ll mod=233333333333333333; struct poi{int too, pre;}e[maxn<<1]; int n, x, y, N, tot, sum, skip, ANS, ANSNUM; int c[maxn], last[maxn], son[maxn], size[maxn], cnt[maxn], ans[maxn]; ll b[maxn], hs[maxn]; char s[maxn]; inline void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;} void dfs1(int x, int fa) { size[x]=1; b[x]=hs[x]=(hs[fa]*27+s[x]-'a'+1)%mod; for(int i=last[x], too;i;i=e[i].pre) if((too=e[i].too)!=fa) { dfs1(too, x); size[x]+=size[too]; if(size[too]>size[son[x]]) son[x]=too; } } void update(int x, int fa, int delta) { if(delta==1) sum+=(!cnt[hs[x]]); cnt[hs[x]]+=delta; for(int i=last[x], too;i;i=e[i].pre) if((too=e[i].too)!=fa && too!=skip) update(too, x, delta); } void dfs2(int x, int fa, bool heavy) { for(int i=last[x], too;i;i=e[i].pre) if((too=e[i].too)!=fa && too!=son[x]) dfs2(too, x, 0); if(son[x]) dfs2(son[x], x, 1), skip=son[x]; update(x, fa, 1); ans[x]=sum; skip=0; if(!heavy) update(x, fa, -1), sum=0; if(ans[x]+c[x]>ANS) ANS=ans[x]+c[x], ANSNUM=1; else if(ans[x]+c[x]==ANS) ANSNUM++; } int main() { read(n); for(int i=1;i<=n;i++) read(c[i]); scanf("%s", s+1); for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x); dfs1(1, 0); N=n; sort(b+1, b+1+N); N=unique(b+1, b+1+N)-b-1; for(int i=1;i<=n;i++) hs[i]=lower_bound(b+1, b+1+N, hs[i])-b; dfs2(1, 0, 1); printf("%d %d", ANS, ANSNUM); }
还可以hash之后写线段树合并，复杂度$O(NlogN)$。（真的懒得写了T T