mcfx's blog

题解、Writeup、游记和碎碎念

BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡

幽香是全幻想乡里最受人欢迎的萌妹子，这天，是幽香的 2600 岁生日，无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。
粉丝们非常热情，自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。
这时幽香发现了一件非常有趣的事情，太阳花田有 n 块空地。在过去，幽香为了方便，在这 n 块空地之间修建了 n-1 条边将它们连通起来。也就是说，这 n 块空地形成了一个树的结构。
有 n 个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺，他们选择了 c 中颜色的衣服，每种颜色恰好可以用一个 0 到 c-1 之间的整数来表示。并且每个人都站在一个空地上，每个空地上也只有一个人。这样整个太阳花田就花花绿绿了。幽香看到了，感觉也非常开心。
粉丝们策划的一个节目是这样的，选中两个粉丝 A 和 B（A 和 B 可以相同），然后 A 所在的空地到 B 所在的空地的路径上的粉丝依次跳起来（包括端点），幽香就能看到一个长度为 A 到 B 之间路径上的所有粉丝的数目（包括 A 和 B）的颜色序列。一开始大家打算让人一两个粉丝（注意：A,B 和 B,A 是不同的，他们形成的序列刚好相反，比如红绿蓝和蓝绿红）都来一次，但是有人指出这样可能会出现一些一模一样的颜色序列，会导致审美疲劳。
于是他们想要问题，在这个树上，一共有多少可能的不同的颜色序列（子串）幽香可以看到呢？
太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过 20 个。

Input

第一行两个正整数 n,c。表示空地数量和颜色数量。
第二行有 n 个 0 到 c-1 之间，由空格隔开的整数，依次表示第 i 块空地上的粉丝的衣服颜色。（这里我们按照节点标号从小到大的顺序依次给出每块空地上粉丝的衣服颜色）。
接下来 n-1 行，每行两个正整数 u,v，表示有一条连接空地 u 和空地 v 的边。

Output

一行，输出一个整数，表示答案。

Sample Input

7 3
0 2 1 2 1 0 0
1 2
3 4
3 5
4 6
5 7
2 5

建广义 SAM 时，每次会把 last 设为初始节点，那么对于这道题，也可以类似优化。

把每个度数为 1 的节点作为根 dfs，每次 dfs 时记下当前 last，然后在处理完一棵子树后还原 last。

Code

#define _GLIBCXX_IOSTREAM
#include<bits/stdc++.h>

typedef long long ll;

#define N 2000010

struct node
{
    int ma,inc;ll cnt;
    node*link,*nxt[10];
}pool[N*2],*pm=pool+1,*start=pool;

namespace _A{node*lst,*cur,*p,*q,*sq;}
void add(int t)
{
    using namespace _A;
    cur=pm++;
    cur->ma=lst->ma+1;
    for(p=lst;p&&!p->nxt[t];p=p->link)p->nxt[t]=cur;
    if(!p){cur->link=start;goto naive;}
    q=p->nxt[t];
    if(p->ma+1==q->ma){cur->link=q;goto naive;}
    sq=pm++;
    sq->ma=p->ma+1;
    memcpy(sq->nxt,q->nxt,sizeof(q->nxt));
    for(;p&&p->nxt[t]==q;p=p->link)p->nxt[t]=sq;
    sq->link=q->link;
    q->link=sq;
    cur->link=sq;
    naive:lst=cur;
}

struct edge
{
    int to;edge*ne;
}_e[200000],*e=_e,*p[100001];

inline void add(int a,int b)
{
    *e=(edge){b,p[a]};p[a]=e++;
}

int c[100001],deg[100001];

void dfs(int x,int fa)
{
    add(c[x]);
    node*t=_A::lst;
    for(edge*i=p[x];i;i=i->ne)
        if(i->to^fa)
        {
            _A::lst=t;
            dfs(i->to,x);
        }
}

node*q[N*2];

int main()
{
    int n,x,y;
    scanf("%d%*d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",c+i);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        deg[x]++;
        deg[y]++;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=n;i++)if(deg[i]==1)
        _A::lst=start,dfs(i,0);
    for(node*i=pool;i<pm;i++)
        for(int j=0;j<10;j++)if(i->nxt[j])i->nxt[j]->inc++;
    int qe=0;
    for(node*i=pool;i<pm;i++)
        if(!i->inc)i->inc=1e9,q[qe++]=i;
    for(int i=0;i<qe;i++)
        for(int j=0;j<10;j++)if(q[i]->nxt[j])if(!--q[i]->nxt[j]->inc)
            q[i]->nxt[j]->inc=1e9,q[qe++]=q[i]->nxt[j];
    for(int i=qe-1;~i;i--)
    {
        for(int j=0;j<10;j++)if(q[i]->nxt[j])q[i]->cnt+=q[i]->nxt[j]->cnt;
        q[i]->cnt++;
    }
    printf("%lld",start->cnt-1);
}

日期： 2017-02-20
标签： BZOJ SAM
这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/180/ 查看。

mcfx's blog

BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡

Input

Output

Sample Input

Sample Output

HINT

Solution

Code