F

Anonymous
c_cpp
05/05/2026 6:13 PM
5.8 KB
19
Indexable
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast, unroll-loops")
#ifdef ONLINE_JUDGE
    #define debug(...) ((void)0)
#else
    #include "debug.h"
#endif
using namespace std;
using ll = long long;
#define endl '\n'

template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");
private:
	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}
public:
	int v;
	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
	modnum inv() const { modnum res; res.v = minv(v, MOD); return res; }
	friend modnum inv(const modnum& m) { return m.inv(); }
	modnum neg() const { modnum res; res.v = v ? MOD-v : 0; return res; }
	friend modnum neg(const modnum& m) { return m.neg(); }
	modnum operator- () const { return neg(); }
	modnum operator+ () const { return modnum(*this); }
	modnum& operator ++ () { v ++; if (v == MOD) v = 0; return *this; }
	modnum& operator -- () { if (v == 0) v = MOD; v --; return *this; }
	modnum& operator += (const modnum& o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
	modnum& operator -= (const modnum& o) { v -= o.v; if (v < 0) v += MOD; return *this; }
	modnum& operator *= (const modnum& o) { v = int(ll(v) * ll(o.v) % MOD); return *this; }
	modnum& operator /= (const modnum& o) { return *this *= o.inv(); }
	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

const int MOD = 1e9 + 7;
using mint = modnum<MOD>;
template <typename T> mint binpow(T aa, long long b) {
	assert(b >= 0);
	mint a = aa;
	mint r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

template <int N> 
struct counting{
	mint fact[N], inv[N], invfact[N];
	counting() {
		fact[0] = fact[1] = invfact[0] = invfact[1] = inv[1] = 1;
		for (int i = 2; i < N; i++) {
			fact[i] = mint(i) * fact[i - 1];
			inv[i] = mint(0) - mint(MOD / i) * inv[MOD % i];
			invfact[i] = invfact[i - 1] * inv[i];
		}
	}
	mint choose(int n, int r) {
		if (n < 0 || r < 0 || n < r) return mint(0);
		return fact[n] * invfact[n - r] * invfact[r];
	}
	mint stars_and_bars(int n, int k){
		return choose(n + k - 1, k - 1);
	}
	mint P(int n, int r){
        if (n < 0 || r < 0 || r > n) return mint(0);
        return fact[n] * invfact[n - r];
    }
	mint catalan(int n){
        return fact[2 * n] * invfact[n] * invfact[n + 1];
    }
};
const int N = 1e6 + 5;
counting<N> comb;

// DO NOT FORGET TO CHANGE THE MOD
void SOLVE() {
	int n; cin >> n;
    vector<vector<int>> graph(n + 1);
    for(int i = 0, u, v; i < n - 1; i++){
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> sz(n + 1, 1);
    function<void(int, int)> pre =[&] (int u, int p){
        for(auto & v : graph[u]) if(v != p){
            pre(v, u);
            sz[u] += sz[v];
        } 
    };
    pre(1, -1);

    vector<mint> dp(n + 1);
    function<mint(int, int)> dfs =[&] (int u, int p){
        int c = 0;
        mint sum = 0;
        for(auto & v : graph[u]) if(v != p){
            c++;
            sum += dfs(v, u);
        }
        if(!c) return sum;
        dp[u] = (sum + sz[u] - 1) * comb.inv[sz[u] - 1];
        sum += dp[u];
        return sum;
    };
    dfs(1, -1);

    cout << dp[1] << endl;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
    freopen("jumper.in", "r", stdin);
	int o_o = 1; cin >> o_o; while(o_o --)
	SOLVE(); return 0;
}
Editor is loading...
Leave a Comment