Submission #12794351

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define MOD 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
typedef vector<tint> vtint;
typedef vector<vint> vvint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=200050;
//↑templete
ll mod_pow(ll x, ll n, ll mod) {
    if(n == 0) return 1;
    ll res = mod_pow((x * x) % mod, n / 2 , mod);
    if(n & 1) res = (res * x) % mod;
    return res;
}
ll ex[SIZE]={1,0};
ll inv[SIZE]={1,0};
ll comb(ll n, ll r){
    return (ex[n]*inv[n-r]%MOD*inv[r])%MOD;
}
vint node[SIZE];
unordered_map<int, bool> done[SIZE];
unordered_map<int, pll> DP[SIZE];    //DP[a][b] = (a->bの部分木に対する番号の振り方, 部分木のサイズ)
void DFS_1(int now, int prev){  //頂点0から向かう方向のDPテーブルを求める

    ll val=1, siz=1;
    
    for(int next:node[now]){
        if(next == prev)
            continue;
        
        DFS_1(next, now);

        (val*=inv[DP[now][next].second])%=MOD;
        (val*=DP[now][next].first)%=MOD;
        siz+=DP[now][next].second;
    }

    if(prev == -1)
        return;

    DP[prev][now].first=(val*ex[siz-1])%MOD;
    DP[prev][now].second=siz;
    done[prev][now]=1;
}
void DFS_2(int now, int prev){  //nowに入ってくる辺について、DPテーブルを求める

    //入ってくる辺についてDPテーブルを求めるためには、出ていく辺についてすべて求められていなくては駄目

    ll val_prod=1, siz_sum=1;
    for(int next:node[now]){
        (val_prod*=inv[DP[now][next].second])%=MOD;
        (val_prod*=DP[now][next].first)%=MOD;
        siz_sum+=DP[now][next].second;
    }

    for(int next:node[now]){
        if(done[next][now])
            continue;
        
        (val_prod*=ex[DP[now][next].second])%=MOD;
        (val_prod*=mod_pow(DP[now][next].first, MOD-2, MOD))%=MOD;
        siz_sum-=DP[now][next].second;

        DP[next][now].first=(val_prod*ex[siz_sum-1])%MOD;
        DP[next][now].second=siz_sum;
        done[next][now]=1;

        (val_prod*=inv[DP[now][next].second])%=MOD;
        (val_prod*=DP[now][next].first)%=MOD;
        siz_sum+=DP[now][next].second;
    }

    for(int next:node[now]){
        if(next == prev)
            continue;
        DFS_2(next, now);
    }

}

signed main(){
	for(int i=1;i<SIZE;i++){
		ex[i]=ex[i-1]*i%MOD;
	}
	for(int i=1;i<SIZE;i++){
		inv[i]=mod_pow(i,MOD-2,MOD);
	}
	for(int i=1;i<SIZE;i++){
		inv[i]=inv[i-1]*inv[i]%MOD;
	}

    int N;
    cin>>N;
    for(int i=0;i<N-1;i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        node[a].pb(b);
        node[b].pb(a);
    }

    DFS_1(0, -1);
    DFS_2(0, -1);

    // for(int i=0;i<N;i++){
    //     for(int j=0;j<N;j++)
    //         cout<<i<<" "<<j<<" "<<DP[i][j].first<<" "<<DP[i][j].second<<endl;
    // }

    ll ans=0;
    for(int now=0;now<N;now++){

        ll val=1, siz=1;
        
        for(int next:node[now]){
            (val*=inv[DP[now][next].second])%=MOD;
            (val*=DP[now][next].first)%=MOD;
            siz+=DP[now][next].second;
        }

        (val*=ex[siz-1])%=MOD;
        (ans+=val)%=MOD;


        cout<<val<<endl;
    }

    //cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result