记录编号	380368	评测结果	AAAAAAAAAA
题目名称	2607.[河南省队2016]九头蛇和时间	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.312 s
提交时间	2017-03-09 07:04:33	内存使用	9.52 MiB

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=100500;
struct SAM{
	int root,val;
	map<int,int> next;
}a[maxn<<1];
int last[maxn],RT,cnt;
int n,root[maxn],du[maxn];
LL ans=0;
int extend(int p,int c){
	int np=++cnt;
	a[np].val=a[p].val+1;
	while(p && !a[p].next[c]){
		a[p].next[c]=np;
		p=a[p].root;
	}
	if(!p)a[np].root=RT;
	else{
		int q=a[p].next[c];
		if(a[q].val==a[p].val+1)a[np].root=q;
		else {
			int nq=++cnt;a[nq]=a[q];
			a[nq].val=a[p].val+1;
			a[np].root=a[q].root=nq;
			while(p && a[p].next[c]==q){
				a[p].next[c]=nq;
				p=a[p].root;
			}
		}
	}
	ans+=a[np].val-a[a[np].root].val;
	return np;
}
struct Edge{
	int next,to;
}e[maxn<<1];
int len,head[maxn];
void Insert(int x,int y){
	len++;e[len].to=y;e[len].next=head[x];head[x]=len;du[x]++;
}
void Dfs(int x){
	last[x]=extend(last[root[x]],du[x]);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(root[x]!=j){
			root[j]=x;
			Dfs(j);
		}
	}
}
void Init();
int main(){
	freopen("af_time.in","r",stdin);freopen("af_time.out","w",stdout);
	Init();
	return 0;
}
void Init(){
	last[0]=RT=++cnt;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;scanf("%d%d",&x,&y);
		Insert(x,y);Insert(y,x);
	}
	Dfs(RT);
	printf("%lld\n",ans);
}