This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz
#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y)
{
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y)
{
x = y;
return true;
}
return false;
}
const int MOD = 1e9 + 7; //998244353
template<class X, class Y>
void add(X &x, const Y &y) {
x = (x + y);
if(x >= MOD) x -= MOD;
}
template<class X, class Y>
void sub(X &x, const Y &y) {
x = (x - y);
if(x < 0) x += MOD;
}
/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
const ll INF = 1e9;
const int N = 100 + 10;
template <typename T> T mod_inv_in_range(T a, T m) {
// assert(0 <= a && a < m);
T x = a, y = m;
T vx = 1, vy = 0;
while (x) {
T k = y / x;
y %= x;
vy -= k * vx;
std::swap(x, y);
std::swap(vx, vy);
}
assert(y == 1);
return vy < 0 ? m + vy : vy;
}
template <typename T> T mod_inv(T a, T m) {
a %= m;
a = a < 0 ? a + m : a;
return mod_inv_in_range(a, m);
}
template <int MOD_> struct modnum {
static constexpr int MOD = MOD_;
static_assert(MOD_ > 0, "MOD must be positive");
using ll = long long;
int v;
public:
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 = mod_inv_in_range(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 -= MOD-o.v;
v = (v < 0) ? v + MOD : v;
return *this;
}
modnum& operator -= (const modnum& o) {
v -= o.v;
v = (v < 0) ? v + MOD : v;
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; }
};
using num = modnum<MOD>;
int par[N];
int find_par(int u) {
if(par[u] < 0) return u;
par[u] = find_par(par[u]);
return par[u];
}
bool merge(int u, int v) {
u = find_par(u), v = find_par(v);
if(u == v) return false;
if(par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
vector<int> g[N];
vector<pii> d[N];
int depth[N];
num pw[N];
bool used[N];
int r[N][N];
void dfs(int u) {
for(auto v : g[u]) {
if(v != par[u]) {
par[v] = u;
depth[v] = depth[u] + 1;
dfs(v);
}
}
}
void BaoJiaoPisu() {
int n, m, k; cin >> n >> m >> k;
for(int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
depth[1] = 1;
dfs(1);
for(int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
if(depth[u] > depth[v]) swap(u, v);
while(depth[v] > depth[u]) {
d[i].pb(mp(v, par[v]));
v = par[v];
}
while(u != v) {
d[i].pb(mp(u, par[u]));
d[i].pb(mp(v, par[v]));
u = par[u];
v = par[v];
}
}
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= m; j++) {
for(auto [u, v] : d[i]) {
for(auto [x, y] : d[j]) {
if(u > v) swap(u, v);
if(x > y) swap(x, y);
if(u == x && y == v) r[i][j] = true;
}
}
}
}
pw[0] = 1;
for(int i = 1; i < n; i++) pw[i] = pw[i - 1] * k;
num ans = pw[n - 1];
for(int msk = 1; msk < (1 << m); msk++) {
for(int i = 1; i <= n; i++) used[i] = false;
for(int i = 1; i <= m; i++) par[i] = -1;
for(int i = 0; i < m; i++) {
if(msk >> i & 1) {
for(int j = i + 1; j < m; j++) {
if(msk >> j & 1) {
if(r[i + 1][j + 1]) merge(i + 1, j + 1);
}
}
for(auto [u, v] : d[i + 1]) {
if(depth[u] > depth[v]) swap(u, v);
used[v] = true;
}
}
}
int c = n - 1;
for(int i = 1; i <= n; i++) c -= used[i];
for(int i = 1; i <= m; i++) {
if((msk >> (i - 1) & 1) && find_par(i) == i) ++c;
}
ans += (btpc(msk) & 1 ? -pw[c] : pw[c]);
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1, ddd = 0;
// cin >> tc;
while(tc--) {
//ddd++;
//cout << "Case #" << ddd << ": ";
BaoJiaoPisu();
}
}
Compilation message (stderr)
Main.cpp: In function 'void BaoJiaoPisu()':
Main.cpp:230:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
230 | for(auto [u, v] : d[i]) {
| ^
Main.cpp:231:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
231 | for(auto [x, y] : d[j]) {
| ^
Main.cpp:254:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
254 | for(auto [u, v] : d[i + 1]) {
| ^
Main.cpp: In function 'int main()':
Main.cpp:277:17: warning: unused variable 'ddd' [-Wunused-variable]
277 | int tc = 1, ddd = 0;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |