题意：一个无向树的度数为 2的结点称为假结点，其它结点称为真结点。一个无向树的简化树
其结点由原树的全体真结点组成，两个真结点之间有边当且仅当它们在原树中有边，或者在
原树中有一条联结这两个结点的路，其中间节点全是假结点。两个无向树各自的简化树如果
同构，即存在结点之间的一一对应，使得在一个树中的任意两个结点之间有边当且仅当它们
的对应结点在另一个树中有边，则称原来的两个无向树实质同构。给定若干个无向树，将相
互实质同构的无向树只保留一个其余删除。统计剩下的相互不实质同构的无向树个数，并将
它们的简化树结点个数从小到大输出。
cas<=20 n<=10000
思路：把很久以前在另一个地方写的题解搬过来
定义题。做法请看题目。
删除假节点并连边：先按输入构图并统计每个点的度数 找一个度不为2的点做一遍dfs
if d[v]=2 f[find(u)]=f[find(v)]
做完之后重连所有f[x[i]]<>f[y[i]]的边
同构：
哈希，将点上的哈希初值都=1，对于点u，取与u相连的点权V并排序，随意哈希作为新的哈希值。迭代10000000000000000000000000000000次。最后只需判断哈希值是否相等。
1 const mo=1000000007; 2 var head,vet,next,d,b,x,y,e1,q,f:array[0..20000]of longint; 3 hash,s,c,h:array[1..20000]of int64; 4 cas,v1,e,v,i,tot,len,n,j,k,ans:longint; 5 tmp:int64; 6 p:boolean; 7 8 procedure qsort(l,r:longint); 9 var i,j:longint; 10 t,mid:int64; 11 begin 12 i:=l; j:=r; mid:=q[(l+r)>>1]; 13 repeat 14 while mid>q[i] do inc(i); 15 while mid<q[j] do dec(j); 16 if i<=j then 17 begin 18 t:=q[i]; q[i]:=q[j]; q[j]:=t; 19 inc(i); dec(j); 20 end; 21 until i>j; 22 if l<j then qsort(l,j); 23 if i<r then qsort(i,r); 24 end; 25 26 function find(k:longint):longint; 27 begin 28 if f[k]<>k then f[k]:=find(f[k]); 29 find:=f[k]; 30 end; 31 32 procedure add(a,b:longint); 33 begin 34 inc(tot); 35 next[tot]:=head[a]; 36 vet[tot]:=b; 37 head[a]:=tot; 38 end; 39 40 procedure dfs(u,fa:longint); 41 var e,v:longint; 42 begin 43 e:=head[u]; 44 while e<>0 do 45 begin 46 v:=vet[e]; 47 if v<>fa then 48 begin 49 if d[v]=2 then f[find(v)]:=f[find(u)]; 50 dfs(v,u); 51 end; 52 e:=next[e]; 53 end; 54 end; 55 56 begin 57 58 readln(cas); 59 60 for v1:=1 to cas do 61 begin 62 read(n); 63 fillchar(head,sizeof(head),0); 64 fillchar(b,sizeof(b),0); 65 fillchar(d,sizeof(d),0); 66 for i:=1 to n do hash[i]:=1; 67 for i:=1 to n do f[i]:=i; 68 tot:=0; 69 for i:=1 to n-1 do 70 begin 71 read(x[i],y[i]); 72 inc(d[x[i]]); inc(d[y[i]]); 73 add(x[i],y[i]); 74 add(y[i],x[i]); 75 end; 76 for i:=1 to n do 77 if d[i]<>2 then 78 begin 79 dfs(i,-1); 80 break; 81 end; 82 tot:=0; 83 fillchar(head,sizeof(head),0); 84 85 86 for i:=1 to n-1 do 87 if f[x[i]]<>f[y[i]] then 88 begin 89 b[f[x[i]]]:=1; b[f[y[i]]]:=1; 90 add(f[x[i]],f[y[i]]); 91 add(f[y[i]],f[x[i]]); 92 end; 93 for i:=1 to n do 94 if d[i]<>2 then inc(e1[v1]); 95 for i:=1 to 2 do 96 begin 97 for j:=1 to n do h[j]:=hash[j]; 98 for j:=1 to n do 99 if b[j]=1 then 100 begin 101 e:=head[j]; 102 len:=0; 103 while e<>0 do 104 begin 105 v:=vet[e]; 106 inc(len); q[len]:=h[v]; 107 e:=next[e]; 108 end; 109 if len>0 then qsort(1,len); 110 tmp:=0; 111 for k:=1 to len do tmp:=(tmp*10003+q[k]) mod mo; 112 hash[j]:=tmp; 113 114 end; 115 end; 116 len:=0; 117 for i:=1 to n do 118 if b[i]=1 then begin inc(len); q[len]:=hash[i]; end; 119 if len>0 then qsort(1,len); 120 tmp:=0; 121 for i:=1 to len do tmp:=(tmp*10003+q[i]) mod mo; 122 123 s[v1]:=tmp; 124 end; 125 for i:=1 to cas do 126 begin 127 p:=true; 128 for j:=1 to i-1 do 129 if s[i]=s[j] then 130 begin 131 p:=false; break; 132 end; 133 if p then begin inc(ans); c[ans]:=e1[i]; end; 134 end; 135 for i:=1 to ans do q[i]:=c[i]; 136 qsort(1,ans); 137 writeln(ans); 138 for i:=1 to ans-1 do write(q[i],' '); 139 write(q[ans]); 140 141 end.