*题目描述：
*题解：
树哈希+组合数学。对于树的形态相同的子树就一起考虑。
*代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif
#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
#define maxn 500010
#define maxm 1000010
struct Edge
{
int to;
Edge *next, *rev;
}*last[maxn], e[maxm], *ecnt = e;
inline void link(R int a, R int b)
{
*++ecnt = (Edge) {b, last[a], ecnt + 1}; last[a] = ecnt;
*++ecnt = (Edge) {a, last[b], ecnt - 1}; last[b] = ecnt;
}
int rt[2], rtcnt, size[maxn], n, root;
void dfs(R int x, R int fa)
{
size[x] = 1;
R int maxx = 0;
for (R Edge *iter = last[x]; iter; iter = iter -> next)
{
R int pre = iter -> to;
if (pre != fa)
{
dfs(pre, x);
size[x] += size[pre];
cmax(maxx, size[pre]);
}
}
cmax(maxx, n - size[x]);
if (maxx <= n >> 1) rt[rtcnt++] = x;
}
int p[maxn], inp[maxn];
const int mod = 1e9 + 7;
inline int qpow(R int x, R int power)
{
R int base = x, ans = 1;
for ( ; power; power >>= 1, base = 1ll * base * base % mod)
if (power & 1) ans = 1ll * ans * base % mod;
return ans;
}
inline void prepare()
{
R int _ = maxn - 1, tmp = 1;
for (R int i = 2; i <= _; ++i)
tmp = 1ll * tmp * i % mod;
inp[_] = qpow(tmp, mod - 2);
for (R int i = _ - 1; ~i; --i)
inp[i] = 1ll * inp[i + 1] * (i + 1) % mod;
}
inline int C(R long long n, R int m)
{
n %= mod; R long long tmp = 1;
for (R int i = 1; i <= m; ++i) tmp = tmp * (n - i + 1) % mod;
return tmp * inp[m] % mod;
}
inline int cl(R long long n, R int k)
{
return C(n + k - 1, k);
}
//cl表示在n种无限多的物品内取k个的方案数
unsigned long long hash[maxn], hash2[maxn];
int st[maxn], top;
long long f[maxn][2]; //f[x][0..1]表示x节点取或者不取的方案数
inline bool cmp(R int x, R int y)
{
return hash[x] > hash[y];
}
void dp(R int x, R int fa)
{
f[x][0] = f[x][1] = 1ll;
for (R Edge *iter = last[x]; iter; iter = iter -> next)
if (iter -> to != fa)
dp(iter -> to, x);
top = 0;
for (R Edge *iter = last[x]; iter; iter = iter -> next)
if (iter -> to != fa)
st[++top] = iter -> to;
std::sort(st + 1, st + top + 1, cmp);
for (R int i = 1, j; i <= top; i = j)
{
for (j = i + 1; j <= top && hash[st[i]] == hash[st[j]] && hash2[st[i]] == hash2[st[j]]; ++j);
f[x][0] = f[x][0] * cl(f[st[i]][0] + f[st[i]][1], j - i) % mod;
f[x][1] = f[x][1] * cl(f[st[i]][0], j - i) % mod;
}
hash[x] = 123;
for (R int i = 1; i <= top; ++i)
hash[x] = (hash[x] * 1999 + 233 * hash[st[i]]) % 998244353;
hash2[x] = 123;
for (R int i = 1; i <= top; ++i)
hash2[x] = (hash2[x] * 12579 + (hash2[st[i]] * 233)) % mod;
}
int main()
{
// setfile();
n = FastIn(); prepare();
for (R int i = 1; i < n; ++i)
{
R int a = FastIn(), b = FastIn();
link(a, b);
}
dfs(1, 0);
if (rtcnt == 2)
{
R Edge *iter;
for (iter = last[rt[0]]; iter; iter = iter -> next)
if (iter -> to == rt[1])
{
iter -> to = iter -> rev -> to = ++n;
break;
}
*++ecnt = (Edge) {rt[0], last[n], ecnt}; last[n] = ecnt;
*++ecnt = (Edge) {rt[1], last[n], ecnt}; last[n] = ecnt;
root = n;
}
else root = rt[0];
dp(root, 0);
R long long ans;
if (rtcnt == 1)
ans = (f[root][0] + f[root][1]) % mod;
else
{
R int x = rt[0], y = rt[1];
if (hash[x] == hash[y])
ans = f[x][0] * f[y][1] % mod + cl(f[x][0], 2) % mod;
else
ans = (f[x][0] * f[y][0] % mod + f[x][0] * f[y][1] % mod + f[x][1] * f[y][0] % mod) % mod;
}
printf("%lld
", ans % mod );
return 0;
}
/*
input:
6
1 2
1 3
1 4
4 5
4 6
output:
9
*/