记录编号	371410	评测结果	AAAAAAAAAA
题目名称	[河南省队2016]九头蛇和时间	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.511 s
提交时间	2017-02-16 08:40:01	内存使用	2.08 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstdarg>
#include <vector>
#include <queue>
#include <cctype>
#include <algorithm>
#include <map>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
}; using IO::readint; using IO::readc;
#define MAXN 100003
struct node{
  node *link;
  int len;
  __gnu_pbds::cc_hash_table<int, node*>next;
 // map<int, node*>next;
  node(){
    len = 0;
    link = NULL;
  }
}root;
vector<int> G[MAXN];
int deg[MAXN];
long long ans = 0;
node* insert(node *last, int v){
  node *cur = new node();
  cur->len = last->len+1;
  node *p;
  for(p = last; p && !p->next[v]; p = p->link)
    p->next[v] = cur;
  if(!p)cur->link = &root;
  else{
    node *q = p->next[v];
    if(q->len == p->len+1)cur->link = q;
    else{
      node *clone = new node();
      clone->link = q->link;
      clone->len = p->len+1;
      clone->next = q->next;
      for(; p && p->next[v] == q; p = p->link)
        p->next[v] = clone;
      q->link = cur->link = clone;
    }
  }
  ans += cur->len-cur->link->len;
  return cur;
}
void dfs(int u, int f, node *last){
  node *cur = insert(last, deg[u]);
  for(int i = 0; i < G[u].size(); i++){
    int to = G[u][i];if(to != f)dfs(to, u, cur);
  }
}
int main(){
  freopen("af_time.in", "r", stdin);
  freopen("af_time.out", "w", stdout);
  int n = readint();
  for(int i = 1; i < n; i++){
    int u = readint(); int v = readint();
    G[u].push_back(v); G[v].push_back(u);
    deg[u]++, deg[v]++;
  }
  dfs(1, 0, &root);
  printf("%lld\n", ans);
  return 0;
}