【jzoj5052】【旅游路线】【后缀数组】

题目大意

A君准备在Z国进行一次旅行，Z国中有n个城市，城市从1到n进行编号，其中1号城市为Z国首都。Z国的旅行交通网由n-1条单向道路构成，并且从任何一个城市出发都可以通过旅行网到达首都。

一条旅行交通网中的旅行线路，可以用线路上所经过的城市来描述，如{v1,v2,v3,……,vm}，它表示一条经过了m个城市的旅行路线，且城市vi到城市vi+1有一条单向道路相连。

两个城市是相似的，当且仅当他们所连接的道路数相同。

若两条路线{u1,u2,……,up}与{v1,v2,……,vq}，若p=q且∀1 ≤ i ≤ p，城市 u i 与 v i 是相似的，则 A君认为这两条旅行路线也是相似的。

现在A君想知道共有多少种不同的旅行路线，相似的若干条旅行路线只算一种。

解题思路

把度数当作字符集，树上sa，求出每个点往上2^i步的rank，和总的sa，sa相邻两个倍增求出lcp即可。

code

#include<set> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LD double #define LL long long #define ULL unsigned long long #define min(a,b) ((a<b)?a:b) #define max(a,b) ((a>b)?a:b) #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define fr(i,j) for(int i=begin[j];i;i=next[i]) using namespace std; int const mn=1e5+9,mnn=18*1e5+9,mm=20*1e5+9,inf=1e9; int n,m,gra,logn,dep[mn],cnt[mn],a[2][mn],sa[mn],fa[mn][18],begin[mnn],to[mm], next[mm],f[mn][18];LL ans; int *rank=a[0],*ord=a[1]; void insert(int u,int v){ to[++gra]=v; next[gra]=begin[u]; begin[u]=gra; } int num(int x,int y){ return y*n+x; } void dfs(int now){ fr(i,now){ dep[to[i]]=dep[now]+1; dfs(to[i]); } } void sort(){ fo(i,1,m)cnt[i]=0; fo(i,1,n)cnt[rank[i]]++; fo(i,1,m)cnt[i]+=cnt[i-1]; fd(i,n,1)sa[cnt[rank[ord[i]]]--]=ord[i]; } int diff(int x,int y,int z){ return (ord[x]!=ord[y])||(ord[fa[x][z]]!=ord[fa[y][z]]); } int lcp(int u,int v){ int tmp=0; fd(i,logn,0) if(fa[u][i]&&(f[u][i]==f[v][i])) tmp+=1<<i,u=fa[u][i],v=fa[v][i]; return tmp+(f[u][0]==f[v][0]); } int main(){ //freopen("route.in","r",stdin); //freopen("route.out","w",stdout); freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d",&n);int u,v; fo(i,1,n-1){ scanf("%d%d",&u,&v); insert(v,u); fa[u][0]=v;rank[u]++;rank[v]++; } logn=log(n)/log(2); fo(j,1,logn)fo(i,1,n){ fa[i][j]=fa[fa[i][j-1]][j-1]; if(fa[i][j])insert(num(fa[i][j],j),i); } dep[1]=1;dfs(1);LL ans=0; fo(i,1,n)ord[i]=i,ans+=dep[i];m=n; fo(i,1,n)f[i][0]=rank[i]; sort(); for(int w=0,p=0;(p<n)&&(w<=logn);w++){ p=0;fo(i,1,n)if(!fa[i][w])ord[++p]=i; fo(i,1,n)fr(j,num(sa[i],w))ord[++p]=to[j]; sort();swap(rank,ord);rank[sa[1]]=p=1; fo(i,2,n)rank[sa[i]]=p+=diff(sa[i],sa[i-1],w); fo(i,1,n)f[i][w+1]=rank[i];m=p; int bb; bb++; } fo(i,1,n-1)ans-=lcp(sa[i],sa[i+1]); printf("%lld\n",ans); return 0; }