OJ题号：
BZOJ3926、洛谷3346题目大意：
给定一棵带权树，定义两个路径是不同的当且仅当两个路径上的权值构成的串不同，求本质不同的路径个数。思路：
广义后缀自动机。 从每个叶子结点开始DFS，并依次加入到SAM中，对于每个加入的结点，last状态是其父亲节点所在的状态，其余插入过程与普通SAM类似。 每个叶子结点的last状态为root。 询问过程与普通SAM完全相同。1 #include2 #include 3 #include 4 #include 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10 return x;11 }12 const int V=100001;13 std::vector e[V];14 int deg[V];15 inline void add_edge(const int u,const int v) {16 e[u].push_back(v);17 deg[u]++;18 }19 int col[V];20 class GeneralSuffixAutomaton {21 private:22 static const int SIGMA_SIZE=10,MAX_STATE=V<<5;23 struct State {24 int link,go[SIGMA_SIZE],len;25 };26 State s[MAX_STATE];27 int sz,newState(const int l) {28 sz++;29 s[sz].len=l;30 return sz;31 }32 int extend(int p,const int w) {33 int new_p=newState(s[p].len+1);34 while(p&&!s[p].go[w]) {35 s[p].go[w]=new_p;36 p=s[p].link;37 }38 if(!p) {39 s[new_p].link=root;40 } else {41 int q=s[p].go[w];42 if(s[q].len==s[p].len+1) {43 s[new_p].link=q;44 } else {45 int new_q=newState(s[p].len+1);46 memcpy(s[new_q].go,s[q].go,sizeof s[q].go);47 s[new_q].link=s[q].link;48 s[q].link=s[new_p].link=new_q;49 while(p&&s[p].go[w]==q) {50 s[p].go[w]=new_q;51 p=s[p].link;52 }53 }54 }55 return new_p;56 }57 public:58 int root;59 GeneralSuffixAutomaton() {60 root=newState(0);61 }62 void build(const int x,const int par,const int lastptr) {63 int p=extend(lastptr,col[x]);64 for(unsigned i=0;i