记录编号	380949	评测结果	AAAAAAAAAA
题目名称	[河南省队2016]九头蛇和时间	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.309 s
提交时间	2017-03-10 17:39:53	内存使用	14.62 MiB

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=150000;
struct SAM{
	int root,val;
	map<int,int> next;
}a[maxn<<1];
int RT,last[maxn],cnt,n;
struct Edge{
	int next,to;
}e[maxn<<1];
int len,head[maxn],du[maxn];
void Insert(int x,int y){
	len++;e[len].to=y;e[len].next=head[x];head[x]=len;
	du[x]++;
}
LL ans=0;
int extend(int c,int p){
	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;
}
int Head,tail,q[maxn],root[maxn];
void Bfs(){
	Head=tail=0;q[tail++]=RT;
	while(Head^tail){
		int x=q[Head++];
		last[x]=extend(du[x],last[root[x]]);
		for(int i=head[x];i;i=e[i].next){
			int j=e[i].to;
			if(root[x]!=j){
				root[j]=x;
				q[tail++]=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);
	}
	Bfs();
	printf("%lld\n",ans);
}