看到读的人多了还是说一下吧,这个可能不是正解。。。
很遗憾,这篇题解并不会有特别详细的分析(因为懒)
如果没有对每个节点求答案就和TDPC的“木”那题差不多。
由于需要算每个节点,考虑换根(dp)。
令 (f_i) 为 (i) 这个子树里放的方案数,(g_i)为这个子树外面放的方案数。
可得:$$f_i = prodlimits_{j in son_i} C_{rest}^{siz_j} f_j$$其中(rest)为未转移子树中节点的总数,边转移边减。
[g_i = g_{fa} imes C_{n - siz_{to} - 1}^{n - siz_{x}} imes prodlimits_{j in son_{fa}} C_{rest}^{siz_j} f_j
]
但是直接转移 (g) 最坏是 (O(n^2)) 的。
考虑优化:把
[prodlimits_{j in son_{fa}} C_{rest}^{j} f_j
]
拆成 (prodlimits_{j in son_{fa}} C_{rest}^{j}) 和 (prodlimits_{j in son_{fa}} f_j)。
右边的式子可以先把 (f_j) 全部乘起来,再乘以逆元。
对左边的式子,可以发现: (cnt_j) 相同时,这个式子的值也相同。所以可以用(map)判重,保证每种只算一次。
(伪)证:一个节点如果下面一共有(k)个节点,下面最多有约 (sqrt{k}) 个大小互不相同的子树。每个都暴力一下,用去的时间为(O(k))。这样复杂度减小很快,应该很难卡掉。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mit map<int,int>::iterator
#define sit set<int>::iterator
#define itrm(g,x) for(mit g=x.begin();g!=x.end();g++)
#define itrs(g,x) for(sit g=x.begin();g!=x.end();g++)
#define ltype int
#define rep(i,j,k) for(ltype(i)=(j);(i)<=(k);(i)++)
#define rap(i,j,k) for(ltype(i)=(j);(i)<(k);(i)++)
#define per(i,j,k) for(ltype(i)=(j);(i)>=(k);(i)--)
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
#define fastio ios::sync_with_stdio(false)
const int inf=0x3f3f3f3f,mod=1000000007;
const double pi=3.1415926535897932,eps=1e-6;
void chmax(int &x,int y){if(x < y) x = y;}
void chmin(int &x,int y){if(x > y) x = y;}
int n,fac[200005],inv[200005],f[200005],g[200005],root,siz[200005],ans[200005];
vector<int> v[200005];
int qpow(int x,int y){
int res = 1;
while(y){
if(y&1) res = (ll)res * x % mod;
x = (ll)x*x%mod;
y>>=1;
}
return res;
}
int getinv(int x){
return qpow(x, mod - 2);
}
int dfs1(int x,int fa){
siz[x]++;
rap(i,0,v[x].size()){
int to = v[x][i];
if(to == fa) continue;
siz[x] += dfs1(to,x);
}
return siz[x];
}
int C(int x,int y){
if(x < y || x < 0 || y < 0) return 0;
return (ll)fac[x] * inv[y] % mod * inv[x - y] % mod;
}
map<ll,int> vals[200005];
void dfs(int x,int fa){
int cur = 1,rest = siz[x] - 1;
rap(i,0,v[x].size()){
int to = v[x][i];
if(to == fa) continue;
dfs(to,x);
cur = (ll)cur * f[to] % mod * C(rest,siz[to]) % mod;
rest -= siz[to];
}
f[x] = cur;
}
void dfs2(int x,int fa){
ans[x] = (ll) f[x] * g[x] % mod * C(n - 1,siz[x] - 1) % mod;
ll product = 1;
rap(i,0,v[x].size()){
int to = v[x][i];
if(to == fa) continue;
product = product * f[to] % mod;
}
rap(i,0,v[x].size()){
int to = v[x][i];
if(to == fa) continue;
g[to] = (ll)g[x] * C(n - siz[to] - 1,n - siz[x]) % mod;
g[to] = (ll)g[to] * product % mod * getinv(f[to]) % mod;
if(vals[x].find(siz[to]) != vals[x].end()) g[to] = (ll)g[to] * vals[x][siz[to]] % mod;
else {
int rest = siz[x] - 1 - siz[to];ll calcing = 1;
rap(j,0,v[x].size()) if(i != j){
int to2 = v[x][j];
if(to2 == fa) continue;
calcing = (ll) calcing * C(rest, siz[to2]) % mod;
rest -= siz[to2];
}
g[to] = (ll)g[to] * calcing % mod;
vals[x][siz[to]] = calcing;
}
dfs2(to,x);
}
}
int main()
{
scanf("%d",&n);
rep(i,2,n){
int t1,t2;
scanf("%d%d",&t1,&t2);
v[t1].pb(t2);
v[t2].pb(t1);
}
fac[0] = 1;rep(i,1,n) fac[i] = (ll)fac[i-1] * i % mod;
rep(i,0,n) inv[i] = getinv(fac[i]);
rep(i,1,n) if(v[i].size() == 1) {root = i;break;}
g[root] = 1;
dfs1(root,0);
dfs(root,0);
dfs2(root,0);
rep(i,1,n) printf("%d
",ans[i]);
return 0;
}