over 1 year ago

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

给定一棵树和每个节点的颜色,求颜色序列不同的链的个数(AB和BA是不同的),其中叶子节点个数不超过20。

对于每条链一定存在一个叶子节点使得链上的点都是祖辈关系。
叶子节点这么少枚举每个叶子当根,多串建立后缀自动机就好了。

又被卡了数组,又被卡了int.QAQ.

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

const long double pi=acos(-1);

template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}

template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

const int maxn=100005;
const int maxm=10;
const int NUM=20;
int n,m,col[maxn];

namespace G
{
    int last[maxn],deg[maxn],ecnt;
    struct Edge
    {
        int to,nxt;
    }e[maxn<<1];
    void ins(int u,int v)
    {
        e[++ecnt]=(Edge){v,last[u]};
        last[u]=ecnt;
    }
    void GetG()
    {
        rep(i,1,n)
        {
            int u,v;
            sc(u);sc(v);
            deg[u]++;deg[v]++;
            ins(u,v);
            ins(v,u);
        }
    }
}
namespace SAM
{
    int last,tot,pre[maxn*NUM],son[maxn*NUM][maxm],v[maxn*NUM];//2*10^6+2*10^6+2*10^7+2*10^6
 void Init()
    {
        rep(i,0,tot+1)memset(son[i],0,m+1<<2);
        last=tot=1;
    }
    int update(int p,int x)
    {
        int q=son[p][x],nq=++tot;
        v[nq]=v[p]+1;
        memcpy(son[nq],son[q],m<<2);
        pre[nq]=pre[q];
        pre[q]=nq;
        for(;son[p][x]==q;p=pre[p])son[p][x]=nq;
        return nq;
    }
    void ins(int x)
    {
        int p=last,np=++tot;
        v[np]=v[last]+1;
        for(;!son[p][x];p=pre[p])son[p][x]=np;
        if(!p)pre[np]=1;
        else
        {
            int q=son[p][x];
            if(v[q]!=v[p]+1)pre[np]=update(p,x);
            else pre[np]=q;
        }
        last=np;
    }
}
bool vis[maxn];
void dfs(int x)
{
    vis[x]=true;  
    using namespace SAM;
    
    int k=son[last][col[x]];
    if(!k)ins(col[x]);
    else if(v[last]+1!=v[k])last=update(last,col[x]);
    else last=k;

    int backup=last;
    for(int i=G::last[x];i;i=G::e[i].nxt)
    if(!vis[G::e[i].to])
    {
        last=backup;
        dfs(G::e[i].to);
    }
    vis[x]=false;
}
ll count()
{
    using namespace SAM;
    ll ans=0;
    rep(i,1,tot+1)
    ans+=v[i]-v[pre[i]];
    return ans;
}
int main()
{
// freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);
 sc(n);sc(m);
    rep(i,1,n+1)
    sc(col[i]);
    
    G::GetG();
    SAM::Init();
    
    rep(i,1,n+1)
    if(G::deg[i]==1)
    {
        SAM::last=1;
        dfs(i);
    }
    ptn(count());
    return 0;
}
← 回文自动机试水