4.2 省选模拟赛旅行路线广义SAM

\(n\leq 100000\)

题目上求出多少条本质不同的路线。

首先定义了相似的城市为度数相同的城市。

还定义了两条路线相同当且仅当长度相同且对应位置的城市都是相似的。

考虑这张图的形态 n-1条边且每个点都能到1号点。

不可能出现环因为考虑如果出现环必然 x个点 x条边根据鸽巢原理一个点被孤立了所以这是一棵内向树。

暴力显然是把所有长度相同的路线给拿出来然后去重比对。

如何去重我们考虑把度数相同的点就定义为其度数大小然后很容易利用hash或者暴力进行比对。

进一步的发现这类似于字符串。

可以发现整棵树是一个字典树。问题是求出本质不同的子串个数

建立广义SAM.没了。

考虑字符集1e5 开map 没了...

题解中给了另外一种做法考虑利用树上SA来求。

发现树上后缀排列不易。最后统计答案也是两个相邻排名的串统计的。

考虑枚举两个相邻排名的串然后统计一下LCP即可。

LCP可以hash+倍增做题解中是倍增做了一发SA我不太明白它是咋做的。

const int MAXN=200010;

int n,cnt=1,len1;ll ans;

int a[MAXN],len[MAXN],f[MAXN];

int lin[MAXN],ver[MAXN],nex[MAXN];

map<int,int>t[MAXN];

inline void add(int x,int y)

{

	ver[++len1]=y;

	nex[len1]=lin[x];

	lin[x]=len1;

	++a[x];++a[y];

}

inline int insert(int x,int last)

{

	int p=last;

	if(t[p].find(x)!=t[p].end())

	{

		int q=t[p][x];

		if(len[q]==len[p]+1)return q;

		int nq=++cnt;

		t[nq]=t[q];f[nq]=f[q];

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

		f[q]=nq;

		while(p&&t[p][x]==q)

		{

			t[p][x]=nq;

			p=f[p];

		}

		return nq;

	}

	int np=last=++cnt;

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

	while(p&&t[p][x]==0)

	{

		t[p][x]=np;

		p=f[p];

	}

	if(!p)f[np]=1;

	else

	{

		int q=t[p][x];

		if(len[q]==len[p]+1)f[np]=q;

		else

		{

			int nq=++cnt;

			t[nq]=t[q];f[nq]=f[q];

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

			f[np]=f[q]=nq;

			while(p&&t[p][x]==q)

			{

				t[p][x]=nq;

				p=f[p];

			}

		}

	}

	ans+=len[np]-len[f[np]];

	return last;

}

inline void dfs(int x,int v)

{

	v=insert(a[x],v);

	go(x)dfs(tn,v);

}

int main()

{

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

	freopen("route.out","w",stdout);

	get(n);

	rep(1,n-1,i)

	{

		int get(x);int get(y);

		add(y,x);

	}

	dfs(1,1);putl(ans);return 0;

}

巴特西

4.2 省选模拟赛旅行路线广义SAM

最新文章

热门文章

巴特西

4.2 省选模拟赛 旅行路线 广义SAM

最新文章

热门文章

4.2 省选模拟赛旅行路线广义SAM