ZJOI2010 诸神眷顾的幻想乡

题目链接：戳我

非常不好意思，因为想要排版，所以今天先只把代码贴出来，明天补题解。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define MAXN 2000010

using namespace std;

int tot=1,n,m,tt;

int du[MAXN],a[MAXN],head[MAXN];

struct Node{int ch[26],ff,len;}t[MAXN<<1];

struct Line{int u,v;}line[MAXN<<1];

struct Edge{int nxt,to;}edge[MAXN<<1];

inline void add(int from,int to){edge[++tt].nxt=head[from],edge[tt].to=to,head[from]=tt;}

inline int extend(int c,int p)

{

    int np=++tot;

    t[np].len=t[p].len+1;

    while(p&&!t[p].ch[c]) t[p].ch[c]=np,p=t[p].ff;

    if(!p) t[np].ff=1;

    else

    {

        int q=t[p].ch[c];

        if(t[q].len==t[p].len+1) t[np].ff=q;

        else

        {

            int nq=++tot;

            t[nq]=t[q];

            t[nq].len=t[p].len+1;

            t[q].ff=t[np].ff=nq;

            while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].ff;

        }

    }

    return np;

}

inline void insert(int x,int pre,int p)

{

    p=extend(a[x],p);

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int v=edge[i].to;

        if(v==pre) continue;

        insert(v,x,p);

    }

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    #endif

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n-1;i++)

    {

        scanf("%d%d",&line[i].u,&line[i].v);

        add(line[i].u,line[i].v),add(line[i].v,line[i].u);

        du[line[i].u]++,du[line[i].v]++;

    }

    for(int i=1;i<=n;i++)

        if(du[i]==1)

            insert(i,0,1);

    long long ans=0;

    for(int i=1;i<=tot;i++)

        ans+=t[i].len-t[t[i].ff].len;

    printf("%lld\n",ans);

    return 0;

}

巴特西

ZJOI2010 诸神眷顾的幻想乡

题目链接：戳我

最新文章

热门文章