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