题意：比较容易懂，就是n个人，构成树形关系。每个人有一条独一无二的信息，每个人可以将自己的信息通过树边，共享给与他相邻的人，共享之后，被共享的人拥有他原有的信息和共享的来的信息。每次共享为一次操作，问每个人都拥有所有人的信息最小要的次数的共享方法有多少种。
做法：参照http://blog.csdn.net/no__stop/article/details/9861649
dfs老是要手动扩栈，听说区域赛的时候可能不能手动扩栈， 于是就学了一下自己手写栈
递归栈：
#pragma comment(linker, "/STACK:2600000,2600000")
#include <cstdio>
#include <cstring>
#define LL long long
const int maxn = 1000000;
const int mod = 1e9 + 7;
int n;
int get_val() {
int ret = 0;
char c;
while ((c = getchar()) == ' ' || c == '\n')
;
ret = c - '0';
while ((c = getchar()) != ' ' && c != '\n')
ret = ret * 10 + c - '0';
return ret;
}
struct Edge {
int v, next;
} edge[maxn << 1];
int head[maxn], E;
void init() {
E = 0;
memset(head, -1, sizeof(int) * (n + 1));
}
void add(int s, int t) {
edge[E].v = t;
edge[E].next = head[s];
head[s] = E++;
edge[E].v = s;
edge[E].next = head[t];
head[t] = E++;
}
int x, y;
int son[maxn];
LL dp[maxn];
LL f[maxn], val[maxn];
int ans;
void ex_gcd(const LL &a, const LL &b, LL &x, LL &y) {
if (!b) {
x = 1;
y = 0;
return;
}
ex_gcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(const int &a) {
LL x, y;
ex_gcd((LL)a, mod, x, y);
if (x < 0)
x += mod;
return x;
}
void dfs(int u, int fa) {
int i, v;
son[u] = 1;
val[u] = 1;
for (i = head[u]; ~i; i = edge[i].next) {
v = edge[i].v;
if (v == fa)
continue;
dfs(v, u);
son[u] += son[v];
val[u] = val[u] * dp[v] % mod * inv(f[son[v]]) % mod;
}
dp[u] = f[son[u] - 1] * val[u] % mod;
}
LL tp;
void dfs2(int u, int fa) {
int i, v;
tp = f[son[1] - 1] * val[u] % mod;
ans += tp * tp % mod;
if (ans > mod)
ans -= mod;
for (i = head[u]; ~i; i = edge[i].next) {
v = edge[i].v;
if (v == fa)
continue;
tp = f[son[1] - son[v] - 1] * val[u] % mod * f[son[v]] % mod
* inv(dp[v]) % mod;
val[v] = val[v] * tp % mod * inv(f[son[1] - son[v]]) % mod;
dfs2(v, u);
}
}
int main() {
int i, cas;
f[0] = 1;
for (i = 1; i <= 1000000; i++)
f[i] = f[i - 1] * i % mod;
cas = get_val();
while (cas--) {
n = get_val();
init();
ans = 0;
for (i = 1; i < n; i++)
add(get_val(), get_val());
dfs(1, 1);
dfs2(1, 1);
printf("%d\n", ans);
}
return 0;
}
手写栈：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define pb push_back
#define LL long long
using namespace std;
const int maxn = 1000000;
const int mod = 1e9 + 7;
int n;
int get_val() {
int ret = 0;
char c;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r')
;
ret = c - '0';
while ((c = getchar()) != ' ' && c != '\n' && c != '\r')
ret = ret * 10 + c - '0';
return ret;
}
struct Edge {
int v, next;
} edge[maxn << 1];
int head[maxn], E;
void init() {
E = 0;
memset(head, -1, sizeof(int) * (n + 1));
}
void add(int s, int t) {
edge[E].v = t;
edge[E].next = head[s];
head[s] = E++;
edge[E].v = s;
edge[E].next = head[t];
head[t] = E++;
}
int x, y;
int son[maxn];
LL dp[maxn];
LL f[maxn], val[maxn];
int ans;
// f[i] = i! s[u] = mult{son[v]!};
// val[u] = siga{dp[v]}
void ex_gcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1;
y = 0;
return;
}
ex_gcd(b, a % b, y, x);
y -= a / b * x;
}
inline LL inv(LL a) {
LL x, y;
ex_gcd(a, mod, x, y);
if (x < 0)
x += mod;
return x;
}
int st[maxn];
bool vis[maxn];
int cur[maxn];
int *top;
int v, t;
void dfs(int u) {
top = st;
*++top = u;
while (top != st) {
u = *top;
if (!vis[u]) {
vis[u] = 1;
son[u] = 1;
val[u] = 1;
}
int &i = cur[u];
for (; ~i; i = edge[i].next) {
v = edge[i].v;
if (!vis[v]) break;
}
if (i == -1 ) {
dp[u] = f[son[u] - 1] * val[u] % mod;
if((top-1) != st) {
t = *(top-1);
son[t] += son[u];
val[t] = val[t] * dp[u] % mod * inv(f[son[u]])% mod;
}
top--;
}
else
*++top = v;
}
}
LL tp;
void dfs2(int u) {
top = st;
*++top = u;
vis[1] = 1;
while (top != st) {
u = *top;
if (!vis[u]) {
vis[u] = 1;
tp = f[son[1] - 1] * val[u] % mod;
ans += tp * tp % mod;
if (ans > mod) ans -= mod;
}
int &i = cur[u];
for (; ~i; i = edge[i].next) {
v = edge[i].v;
if (!vis[v]) {
tp = f[son[1] - son[v] - 1] * val[u] % mod * f[son[v]] % mod
* inv(dp[v]) % mod;
val[v] = val[v] * tp % mod * inv(f[son[1] - son[v]]) % mod;
break;
}
}
if (i == -1 )
top--;
else
*++top = v;
}
}
int main() {
int i, cas;
f[0] = 1;
for (i = 1; i <= 1000000; i++)
f[i] = f[i - 1] * i % mod;
cas = get_val();
while (cas--) {
n = get_val();
init();
ans = 0;
for (i = 1; i < n; i++) {
add(get_val(), get_val());
}
for(i = 1; i <= n; i++) {
vis[i] = 0;
cur[i] = head[i];
}
dfs(1);
ans += dp[1] * dp[1] % mod;
if (ans > mod)
ans -= mod;
for(i = 1; i <= n; i++) {
vis[i] = 0;
cur[i] = head[i];
}
for (i = head[1]; ~i; i = edge[i].next) {
int v = edge[i].v;
int tp = f[son[1] - son[v] - 1] * f[son[v]] % mod * val[1] % mod
* inv(dp[v]) % mod;
val[v] = val[v] * tp % mod * inv(f[son[1] - son[v]]) % mod;
dfs2(v);
}
printf("%d\n", ans);
}
return 0;
}