fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define For(i, a, b) for (int i = (a); i <= (b); ++i)
  4. #define ForD(i, a, b) for (int i = (a); i >= (b); --i)
  5. #define rep(i, n) for (int i = 0; i < (n); ++i)
  6. #define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
  7. #define pb push_back
  8.  
  9. #define vi vector<int>
  10.  
  11. #define int long long
  12.  
  13. using namespace std;
  14.  
  15. void file(string s){
  16.  
  17.     if (s.empty()) return;
  18.  
  19.     freopen((s + ".inp").c_str(), "r", stdin);
  20.     freopen((s + ".out").c_str(), "w", stdout);
  21. }
  22.  
  23. const int N = 70 + 5;
  24. const int MOD = 1e9 + 7; //998244353;
  25.  
  26. int n, m, k, Pow[N], x[N], y[N], par[N];
  27. vi g[N];
  28. int up[N], h[N], Lca[N];
  29.  
  30. void add(int &x, int y){
  31.     x += y;
  32.     if (x >= MOD) x -= MOD;
  33.     if (x < 0) x += MOD;
  34. }
  35.  
  36. int mul(int x, int y){
  37.     return x * y % MOD;
  38. }
  39.  
  40. void dfs(int u){
  41.     for (int v: g[u]) if (v != up[u])
  42.         up[v] = u, h[v] = h[u] + 1, dfs(v);
  43. }
  44.  
  45. int lca(int u, int v){
  46.     while (h[v] > h[u]) v = up[v];
  47.     while (u != v) u = up[u], v = up[v];
  48.     return u;
  49. }
  50.  
  51. int find(int u){
  52.     return par[u] < 0 ? u : par[u] = find(par[u]);
  53. }
  54.  
  55. void Union(int u, int v){
  56.     u = find(u); v = find(v);
  57.     if (u == v) return;
  58.     if (h[u] > h[v]) swap(u, v);
  59.     par[u] += par[v];
  60.     par[v] = u;
  61. }
  62.  
  63. void add(int i){
  64.     int u = x[i], v = y[i];
  65.  
  66.     while (h[u] > h[Lca[i]] + 1){
  67.         Union(u, up[u]);
  68.         u = up[u];
  69.     }
  70.     while (h[v] > h[Lca[i]] + 1){
  71.         Union(v, up[v]);
  72.         v = up[v];
  73.     }
  74.  
  75.     if (u != Lca[i]) Union(u, v);
  76. }
  77.  
  78. signed main(){
  79.  
  80.     ios_base::sync_with_stdio(0); 
  81.     cin.tie(0); cout.tie(0);
  82.     file("coloring");
  83.  
  84.     cin >> n >> m >> k;
  85.     rep(i, n - 1){
  86.         int u, v; cin >> u >> v;
  87.         g[u].pb(v); g[v].pb(u);
  88.     }
  89.  
  90.     dfs(1);
  91.  
  92.     rep(i, m){
  93.         cin >> x[i] >> y[i];
  94.         if (h[x[i]] > h[y[i]]) swap(x[i], y[i]);
  95.         if (x[i] == y[i]) return cout << 0, 0;
  96.         Lca[i] = lca(x[i], y[i]);
  97.     }
  98.  
  99.     Pow[0] = 1;
  100.     For(i, 1, n - 1) Pow[i] = Pow[i - 1] * k % MOD;
  101.  
  102.     int res = 0;
  103.     rep(msk, 1 << m){
  104.         memset(par, -1, sizeof par);
  105.         rep(i, m) if (msk & (1 << i))
  106.             add(i);
  107.  
  108.         int cnt = 0; 
  109.         For(i, 2, n) cnt += (par[i] < 0);
  110.  
  111.         if (!(__builtin_popcount(msk) & 1))
  112.             add(res, Pow[cnt]); 
  113.         else
  114.             add(res, -Pow[cnt]);
  115.     }
  116.  
  117.     cout << res;    
  118.  
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dIhTnR
language:
C++14 (gcc 8.3)
created:
20 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!