AhmedAshraff

Untitled

Aug 1st, 2025
453
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
  4. #define ll long long
  5. #define sz(s) (int)(s).size()
  6. #define all(s) (s).begin(),(s).end()
  7. using namespace std;
  8.  
  9. void File();
  10.  
  11. void sol();
  12.  
  13. const int mod = 1e9 + 7, N = 1e6 + 5;
  14.  
  15. int add(int a, int b) {
  16.     return (a + b) % mod;
  17. }
  18.  
  19. int mul(int a, int b) {
  20.     return 1ll * a * b % mod;
  21. }
  22.  
  23. int sub(int a, int b) {
  24.     return add(a, mod - b);
  25. }
  26.  
  27. int fp(int a, int p) {
  28.     if (!p)return 1;
  29.     int ret = fp(a, p >> 1);
  30.     ret = mul(ret, ret);
  31.     if (p & 1)ret = mul(ret, a);
  32.     return ret;
  33. }
  34.  
  35. int pref[N], pref_inc[N], pref_dec[N];
  36.  
  37. void init() {
  38.     pref[0] = pref_inc[0] = pref_dec[0] = 0;
  39.     for (int i = 1; i < N; i++) {
  40.         int iv = fp(i, mod - 2);
  41.         pref[i]     = add(pref[i - 1], iv);
  42.         pref_inc[i] = add(pref_inc[i - 1], mul(i, iv));
  43.         pref_dec[i] = add(pref_dec[i - 1], mul(N - i, iv));
  44.     }
  45. }
  46.  
  47. class LCA {
  48.     int n, logN, root = 1;
  49.     vector<int> depth;
  50.     vector<vector<int>> adj, lca;
  51.  
  52.     void dfs(int node, int parent) {
  53.         lca[node][0] = parent;
  54.         depth[node] = (~parent ? depth[parent] + 1 : 0);
  55.         for (int k = 1; k <= logN; k++) {
  56.             int up_parent = lca[node][k - 1];
  57.             if (~up_parent)
  58.                 lca[node][k] = lca[up_parent][k - 1];
  59.         }
  60.         for (int child: adj[node])
  61.             if (child != parent)
  62.                 dfs(child, node);
  63.     }
  64.  
  65. public:
  66.     LCA(const vector<vector<int>> &_adj, int root = 1) : root(root), adj(_adj) {
  67.         adj = _adj;
  68.         n = adj.size() - 1;
  69.         logN = log2(n);
  70.         lca = vector<vector<int>>(n + 1, vector<int>(logN + 1, -1));
  71.         depth = vector<int>(n + 1);
  72.         dfs(root, -1);
  73.     }
  74.  
  75.     int get_LCA(int x, int y) {
  76.         if (depth[x] < depth[y])
  77.             swap(x, y);
  78.         for (int k = logN; k >= 0; k--)
  79.             if (depth[x] - (1 << k) >= depth[y])
  80.                 x = lca[x][k];
  81.         if (x == y)
  82.             return x;
  83.         for (int k = logN; k >= 0; k--) {
  84.             if (lca[x][k] != lca[y][k]) {
  85.                 x = lca[x][k], y = lca[y][k];
  86.             }
  87.         }
  88.         return lca[x][0];
  89.     }
  90.  
  91.     int get_distance(int u, int v) {
  92.         return depth[u] + depth[v] - 2 * depth[get_LCA(u, v)];
  93.     }
  94.  
  95.     int shifting(int node, int dist) {
  96.         for (int i = logN; i >= 0 && ~node; i--)
  97.             if (dist & (1 << i))
  98.                 node = lca[node][i];
  99.         return node;
  100.     }
  101. };
  102.  
  103. int main() {
  104.     boAshraf
  105.     File();
  106.     int t = 1;
  107.     cin >> t;
  108.     init();
  109.     while (t--) {
  110.         sol();
  111.     }
  112.     return 0;
  113. }
  114.  
  115. void sol() {
  116.     int n, m, q;
  117.     cin >> n >> m >> q;
  118.     vector<bool> infected(n + 1);
  119.     for (int i = 0; i < m; ++i) {
  120.         int u;
  121.         cin >> u;
  122.         infected[u] = 1;
  123.     }
  124.     vector<vector<int>> adj(n + 1);
  125.     for (int i = 0; i < n - 1; ++i) {
  126.         int u, v;
  127.         cin >> u >> v;
  128.         adj[u].emplace_back(v);
  129.         adj[v].emplace_back(u);
  130.     }
  131.     LCA lc(adj);
  132.     vector<int> near_inf(n + 1, -1);
  133.     auto dfs = [&](auto &self, int u, int p, int inf) -> void {
  134.         if (infected[u])inf = u;
  135.         near_inf[u] = inf;
  136.         for (auto v: adj[u]) {
  137.             if (v == p)continue;
  138.             self(self, v, u, inf);
  139.         }
  140.     };
  141.     dfs(dfs, 1, 0, -1);
  142.     auto calc = [&](int u, int before, int after) -> int {
  143.         if (u < 0) return 0;
  144.         int tot = before + after + 1;
  145.         int mx = min(before, after) + 1;
  146.         assert(mx>0);
  147.         int sum = pref_inc[mx];
  148.         int l = tot - mx + 1;
  149.         int r = tot;
  150.         sum = add(sum, sub(pref_dec[r], pref_dec[l - 1]));
  151.         sum = add(sum, mul(sub(pref[r], pref[l - 1]), sub(1 + tot, N)));
  152.         r = l - 1; l = mx + 1;
  153.         if (l <= r) {
  154.             sum = add(sum, mul(mx, sub(pref[r], pref[l - 1])));
  155.         }
  156.         if (before == after) {
  157.             sum = sub(sum, mul(mx, sub(pref[mx], pref[mx - 1])));
  158.         }
  159.         return sum;
  160.     };
  161.     while (q--) {
  162.         int u, v, ans = 0;
  163.         cin >> u >> v;
  164.         if (u == v) {
  165.             cout << (infected[u] ? 1 : 0) << '\n';
  166.             continue;
  167.         }
  168.         int L = lc.get_LCA(u, v);
  169.         vector<int> d;
  170.         if (L == u || L == v) {
  171.             if (L == v)swap(u, v);
  172.             d.emplace_back(v);
  173.         }
  174.         else {
  175.             d.emplace_back(u);
  176.             d.emplace_back(v);
  177.         }
  178.  
  179.         if(infected[L])
  180.             ans = add(ans, calc(L, lc.get_distance(L,u),lc.get_distance(L,v)));
  181.  
  182.         for (auto x: d) {
  183.             while (true) {
  184.                 x = near_inf[x];
  185.                 if (x == -1 || x==L || lc.get_LCA(x,L)!=L)break;
  186.                 ans = add(ans, calc(x, lc.get_distance(x,u),lc.get_distance(x,v)));
  187.                 x = lc.shifting(x, 1);
  188.             }
  189.         }
  190.         cout<<ans<<'\n';
  191.     }
  192. }
  193.  
  194. void File() {
  195. #ifndef ONLINE_JUDGE
  196.     freopen("input.txt", "r", stdin);
  197.     freopen("output.txt", "w", stdout);
  198. #endif
  199. }
  200.  
Advertisement
Add Comment
Please, Sign In to add comment