BZOJ 3926 ZJOI2015 诸神眷顾的幻想乡

Description

幽香是全幻想乡里最受人欢迎的萌妹子,这天,是幽香的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

Sample Output

30

HINT

对于所有数据,1<=n<=100000, 1<=c<=10。

Solution

转换题目意思,就是求一颗Trie树上不同子串个数。
怎么处理子串问题呢,我们想到了神奇的后缀自动机!
但是怎么在Trie树上建立一颗后缀自动机呢?
这个我实在太弱辣!说不太清楚,感兴趣的读者可以参阅2015国家集训队论文集中刘研绎的《后缀自动机在字典树上的拓展》以及张天扬的《后缀自动机及其应用》,在这里我就不详细展开了,只讲一讲怎么搞吧。
我们可以DFS一颗Trie树,每DFS到一个点,就向SAM中插入这个点,注意插入的位置——last,它作用在当前的DFS中,也就是说,当前的Trie树节点连接的所有子节点,具有相同的插入位置。
Trie树我们建好了,怎么解决题目呢?
注意到“只与一个空地相邻的空地数量不超过20个。”这个条件,这等于说叶子节点最多20个。
我们可以对每个叶子节点都建一颗Trie,在这棵Trie上不同的子串数目就是答案。
最后把这么一些Trie的答案加一加就可以了。

代码:

/**************************************************************
    Problem: 3926
    User: MagHSK
    Language: C++
    Result: Accepted
    Time:2380 ms
    Memory:197220 kb
****************************************************************/

#include <cstdio>
int getint() {
    int r = 0;
    char c = getchar();
    for(; c < '0' || '9' < c; c = getchar());
    for(; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r;
}
const int maxn = 100005;
int n, c;
struct Edge {
    int to, next;
} edge[maxn << 1];

int par[maxn * 40], trans[maxn * 40][10];
int len[maxn * 40], tot = 1;
int col[maxn], cnte = 0, h[maxn], du[maxn];
void ins(int u, int v) { edge[++cnte].to = v; edge[cnte].next = h[u]; h[u] = cnte; }
int SAM_extend(int x, int p) {
    int np = ++tot;
    len[np] = len[p] + 1;
    while (p && trans[p][x] == 0) {
        trans[p][x] = np;
        p = par[p];
    }
    if (!p) par[np] = 1;
    else {
        int q = trans[p][x];
        if (len[q] == len[p] + 1) par[np] = q;
        else {
            int nq = ++tot;
            len[nq] = len[p] + 1;
            for (int i = 0; i < 10; ++i) trans[nq][i] = trans[q][i];
            par[nq] = par[q];
            par[q] = par[np] = nq;
            while (p && trans[p][x] == q) {
                trans[p][x] = nq;
                p = par[p];
            }
        }
    }
    return np;
}
void dfs(int now, int fa, int p) {
    p = SAM_extend(col[now], p);
    for (int i = h[now]; i; i = edge[i].next) if (fa != edge[i].to) dfs(edge[i].to, now, p);
}
long long ans = 0;
int main () {
    n = getint(); c = getint();
    for (int i = 1; i <= n; ++i) col[i] = getint();
    int u, v;
    for (int i = 1; i < n; ++i) {
        u = getint();
        v = getint();
        ins(u, v);
        ins(v, u);
        ++ du[u];
        ++ du[v];
    }
    for (int i = 1; i <= n; ++i) if (du[i] == 1) dfs(i, 0, 1);
    for (int i = 2; i <= tot; ++i) ans += (long long)(len[i] - len[par[i]]);
    printf("%lld", ans);
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据