Advertisement
Dang_Quan_10_Tin

COLOUR

May 26th, 2022
483
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "COLOUR"
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. using ld = long double;
  10.  
  11. constexpr int N = 2e5 + 5;
  12. constexpr int mod = 1e9 + 7;
  13. int n, m, q;
  14.  
  15. int ranks[N], par[N][18];
  16. vector<int> adj[N];
  17. ll Pow[N], f[N][2];
  18.  
  19. void Read()
  20. {
  21.     cin >> n >> m >> q;
  22.  
  23.     for (int i = 1; i < n; ++i)
  24.     {
  25.         int u, v;
  26.         cin >> u >> v;
  27.  
  28.         adj[u].emplace_back(v);
  29.         adj[v].emplace_back(u);
  30.     }
  31. }
  32.  
  33. void dfs(int v)
  34. {
  35.     for (int i = 1; i < 18; ++i)
  36.         par[v][i] = par[par[v][i - 1]][i - 1];
  37.  
  38.     for (auto i : adj[v])
  39.         if (!ranks[i])
  40.         {
  41.             ranks[i] = ranks[v] + 1;
  42.             par[i][0] = v;
  43.  
  44.             dfs(i);
  45.         }
  46. }
  47.  
  48. int LCA(int u, int v)
  49. {
  50.     if (ranks[u] < ranks[v])
  51.         swap(u, v);
  52.  
  53.     for (int i = 17; ~i; --i)
  54.         if (ranks[par[u][i]] >= ranks[v])
  55.             u = par[u][i];
  56.     for (int i = 17; ~i; --i)
  57.         if (par[u][i] != par[v][i])
  58.         {
  59.             u = par[u][i];
  60.             v = par[v][i];
  61.         }
  62.  
  63.     return u == v ? u : par[u][0];
  64. }
  65.  
  66. int d(int u, int v)
  67. {
  68.     return ranks[u] + ranks[v] - ranks[LCA(u, v)] * 2;
  69. }
  70.  
  71. void Solve()
  72. {
  73.     ranks[1] = 1;
  74.     dfs(1);
  75.  
  76.     Pow[0] = 1;
  77.     f[1][1] = m;
  78.  
  79.     for (int i = 1; i <= n; ++i)
  80.     {
  81.         Pow[i] = Pow[i - 1] * (m - 1) % mod;
  82.         if (i > 1)
  83.         {
  84.             f[i][0] = (f[i - 1][1] * (m - 1) + f[i - 1][0] * (m - 2)) % mod;
  85.             f[i][1] = f[i - 1][0];
  86.         }
  87.     }
  88.  
  89.     while (q--)
  90.     {
  91.         int u, v;
  92.         cin >> u >> v;
  93.  
  94.         int dis = d(u, v) + 1;
  95.  
  96.         cout << f[dis][0] * Pow[n - dis] % mod << "\n";
  97.     }
  98. }
  99.  
  100. int32_t main()
  101. {
  102.     ios_base::sync_with_stdio(0);
  103.     cin.tie(0);
  104.     cout.tie(0);
  105.  
  106.     if (fopen(task ".INP", "r"))
  107.     {
  108.         freopen(task ".INP", "r", stdin);
  109.         freopen(task ".OUT", "w", stdout);
  110.     }
  111.  
  112.     Read();
  113.     Solve();
  114. }
  115.  
  116. /*
  117. 5 2 3
  118. 1 2
  119. 3 4
  120. 1 4
  121. 2 5
  122. 2 3
  123. 4 5
  124. 5 3
  125. */
Advertisement
RAW Paste Data Copied
Advertisement