题目大意

给定一棵 n 个节点的树，1是根节点。定义 dx 表示点 x 的度数，你需要统计有多少条不同的树链（从点向祖先走的路径）。 两条路径相同当且仅当其长度相同而且对于两条路径各自经过的第i个点 x 和y， dx=dy 。

1≤n≤105

---

题目分析

求出 d 之后可以发现这相当于给定一棵（不严格的）字典树（没有合并相同儿子），要你求本质不同的子串个数。 你可以合并相同儿子之后Trie上建SAM，然后直接用随便一种方法求本质不同的子串个数。当然，在这题，你不一定要合并相同儿子，不过这样子建SAM的话，你最后只能用每个点的 max 减去其 parent 的 max 之和来计算子串个数，因为这样即便是遇到两个意义相同的点，也不会算错。 字符集有点大，使用map来存就好了。 时间复杂度 O(nlogn) 。

---

代码实现

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cctype> #include <queue> #include <map> using namespace std; typedef long long LL; int read() { int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar(); while (isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f; } const int N=100050; const int S=N<<1; namespace SAM { struct node { int prt,len,size; map<int,int> nxt; }sam[S]; int root,tot; int newnode() { ++tot,sam[tot].prt=sam[tot].len=sam[tot].size=0,sam[tot].nxt.clear(); return tot; } void init(){tot=0,root=newnode();} int insert(int c,int lst) { int np=newnode(),p=lst,q; for (sam[np].len=sam[p].len+1,sam[np].size=1;p&&!sam[p].nxt[c];p=sam[p].prt) sam[p].nxt[c]=np; if (!p) sam[np].prt=root; else if (sam[q=sam[p].nxt[c]].len==sam[p].len+1) sam[np].prt=q; else { int nq=newnode(); sam[nq].prt=sam[q].prt,sam[nq].size=0,sam[nq].nxt=sam[q].nxt; sam[np].prt=sam[q].prt=nq; for (sam[nq].len=sam[p].len+1;p&&sam[p].nxt[c]==q;p=sam[p].prt) sam[p].nxt[c]=nq; } return np; } LL calc(int x) { LL ret=0; for (int x=1;x<=tot;++x) ret+=sam[x].len-sam[sam[x].prt].len; return ret; } }; int d[N],tov[N],nxt[N],last[N],root[N]; queue<int> q; int n,tot; void insert(int x,int y){tov[++tot]=y,nxt[tot]=last[x],last[x]=tot;} void bfs() { int x,i,y; for (SAM::init(),q.push(1),root[1]=SAM::insert(d[1],1);!q.empty();) for (x=q.front(),q.pop(),i=last[x];i;i=nxt[i]) q.push(y=tov[i]),root[y]=SAM::insert(d[y],root[x]); } int main() { freopen("route.in","r",stdin),freopen("route.out","w",stdout); n=read(); for (int i=1,x,y;i<n;++i) x=read(),y=read(),insert(y,x),++d[x],++d[y]; bfs(),printf("%lld\n",SAM::calc(SAM::root)); fclose(stdin),fclose(stdout); return 0; }