Hướng dẫn giải của Bedao Regular Contest 21 - Du lịch trong thành phố Trê


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include <bits/stdc++.h>

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 1606
#endif

using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define pc __builtin_popcount
#define bit(i) 1LL << i

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef string str;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef array<int, 3> iii;
typedef array<ll, 3> lll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
typedef vector<db> vd;

template<typename T> T gcd(T a, T b){return (b == 0? a : gcd(b, a % b));}
template<typename T> T lcm(T a, T b){return a / gcd(a, b) * b;}
template<typename T> T mod(T a, T m){if (a < 0) return a + m; if (a >= m) a -= m; if (a < m) return a; return a % m;}
template<typename T> T minimize(T &x, T const &v){if (x == -1 || x > v){x = v; return true;} return false;}
template<typename T> T maximize(T &x, T const &v){if (x == -1 || x < v){x = v; return true;} return false;}

#define file "fiel"
bool const SINGLE_TEST = true;

int const N = 1e6 + 1;
int const MOD = 1e9 + 7;

int fct[N], inv[N];

int mpow(int x, int n){
    if (n == 0) return 1;
    int ans = mpow(x, n / 2);
    if (n & 1) return 1LL * ans * ans % MOD * x % MOD;
    return 1LL * ans * ans % MOD;
}

void init(){
    fct[0] = inv[0] = 1;
    for (int i = 1; i < N; i++){
        fct[i] = 1LL * fct[i - 1] * i % MOD;
    }
    inv[N - 1] = mpow(fct[N - 1], MOD - 2);
    for (int i = N - 2; i >= 1; i--){
        inv[i] = 1LL * inv[i + 1] * (i + 1) % MOD;
    }
}

int C(int k, int n){
    if (k > n) return 0;
    return 1LL * fct[n] * inv[k] % MOD * inv[n - k] % MOD;
}

int n; 
vi g[N];
int sz[N];
int f_in[N], f_out[N];

int mulC(int v, int p){
    int ans = fct[sz[v] - 1];
    for (auto u: g[v]) if (u != p){
        ans = 1LL * ans * inv[sz[u]] % MOD;
    }
    return ans;
}

void DFS(int v, int p = -1){
    sz[v]++;
    f_in[v] = 1;
    for (auto u: g[v]) if (u != p){
        DFS(u, v);
        sz[v] += sz[u];
        f_in[v] = 1LL * f_in[v] * f_in[u] % MOD; 
    }
    f_in[v] = 1LL * f_in[v] * mulC(v, p) % MOD;
}

void DFS2(int v, int p = -1){
    for (auto u: g[v]) if (u != p){
        f_out[u] = C(n - sz[v], n - sz[u] - 1);
        f_out[u] = 1LL * f_out[u] * f_out[v] % MOD;
        int f_ex = 1LL * f_in[v] * mpow(f_in[u], MOD - 2) % MOD * fct[sz[u]] % MOD * fct[sz[v] - 1 - sz[u]] % MOD * inv[sz[v] - 1] % MOD;
        f_out[u] = 1LL * f_out[u] * f_ex % MOD;
        DFS2(u, v);
    }
}

void solve(){
    init();

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

    DFS(1);
    f_out[1] = 1; 
    DFS2(1);

    for (int i = 1; i <= n; i++){
        cout << 1LL * f_in[i] * f_out[i] % MOD * C(sz[i] - 1, n - 1) % MOD << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);//      the
    cin.tie(0);cout.tie(0);//       magical lines
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    int t;
    if (SINGLE_TEST) t = 1;
    else cin >> t;
    while (t--) solve();
    return 0;
}
/*
khong phai _HDH, _HDH ko xai template!!!
> [14:46] (+07:00) 20.December.2024
*/

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.