「BZOJ3926」[ZJOI2015] 诸神眷顾的幻想乡
陈老师语文水平高超
陈老师的博客：
http://wjmzbmr.com/archives/zjoi-2015-day-1%E9%A2%98%E8%A7%A3/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int n,c,cnt; int v[100005],de[100005],last[100005]; struct edge{ int to,next; }e[200005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; e[++cnt]=(edge){u,last[v]};last[v]=cnt; } struct sam{ int cnt; int fa[4000005],mx[4000005],a[4000005][10]; sam(){ cnt=1; } int extend(int p,int c){ int np=++cnt;mx[np]=mx[p]+1; while(!a[p][c]&&p)a[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else { int q=a[p][c]; if(mx[p]+1==mx[q])fa[np]=q; else { int nq=++cnt;mx[nq]=mx[p]+1; memcpy(a[nq],a[q],sizeof(a[q])); fa[nq]=fa[q]; fa[np]=fa[q]=nq; while(a[p][c]==q)a[p][c]=nq,p=fa[p]; } } return np; } void solve(){ for(int i=1;i<=cnt;i++) ans+=mx[i]-mx[fa[i]]; } }sam; void dfs(int x,int fa,int p) { int t=sam.extend(p,v[x]); for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) dfs(e[i].to,x,t); } int main() { n=read();c=read(); for(int i=1;i<=n;i++)v[i]=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); de[u]++;de[v]++; } for(int i=1;i<=n;i++) if(de[i]==1)dfs(i,0,1); sam.solve(); printf("%lld\n",ans); return 0; } |
Subscribe
计数器 9813867
OI 课件=>
OI 课件=>