Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
- #define ll long long
- #define sz(s) (int)(s).size()
- #define all(s) (s).begin(),(s).end()
- using namespace std;
- void File();
- void sol();
- const int mod = 1e9 + 7, N = 1e6 + 5;
- int add(int a, int b) {
- return (a + b) % mod;
- }
- int mul(int a, int b) {
- return 1ll * a * b % mod;
- }
- int sub(int a, int b) {
- return add(a, mod - b);
- }
- int fp(int a, int p) {
- if (!p)return 1;
- int ret = fp(a, p >> 1);
- ret = mul(ret, ret);
- if (p & 1)ret = mul(ret, a);
- return ret;
- }
- int pref[N], pref_inc[N], pref_dec[N];
- void init() {
- pref[0] = pref_inc[0] = pref_dec[0] = 0;
- for (int i = 1; i < N; i++) {
- int iv = fp(i, mod - 2);
- pref[i] = add(pref[i - 1], iv);
- pref_inc[i] = add(pref_inc[i - 1], mul(i, iv));
- pref_dec[i] = add(pref_dec[i - 1], mul(N - i, iv));
- }
- }
- class LCA {
- int n, logN, root = 1;
- vector<int> depth;
- vector<vector<int>> adj, lca;
- void dfs(int node, int parent) {
- lca[node][0] = parent;
- depth[node] = (~parent ? depth[parent] + 1 : 0);
- for (int k = 1; k <= logN; k++) {
- int up_parent = lca[node][k - 1];
- if (~up_parent)
- lca[node][k] = lca[up_parent][k - 1];
- }
- for (int child: adj[node])
- if (child != parent)
- dfs(child, node);
- }
- public:
- LCA(const vector<vector<int>> &_adj, int root = 1) : root(root), adj(_adj) {
- adj = _adj;
- n = adj.size() - 1;
- logN = log2(n);
- lca = vector<vector<int>>(n + 1, vector<int>(logN + 1, -1));
- depth = vector<int>(n + 1);
- dfs(root, -1);
- }
- int get_LCA(int x, int y) {
- if (depth[x] < depth[y])
- swap(x, y);
- for (int k = logN; k >= 0; k--)
- if (depth[x] - (1 << k) >= depth[y])
- x = lca[x][k];
- if (x == y)
- return x;
- for (int k = logN; k >= 0; k--) {
- if (lca[x][k] != lca[y][k]) {
- x = lca[x][k], y = lca[y][k];
- }
- }
- return lca[x][0];
- }
- int get_distance(int u, int v) {
- return depth[u] + depth[v] - 2 * depth[get_LCA(u, v)];
- }
- int shifting(int node, int dist) {
- for (int i = logN; i >= 0 && ~node; i--)
- if (dist & (1 << i))
- node = lca[node][i];
- return node;
- }
- };
- int main() {
- boAshraf
- File();
- int t = 1;
- cin >> t;
- init();
- while (t--) {
- sol();
- }
- return 0;
- }
- void sol() {
- int n, m, q;
- cin >> n >> m >> q;
- vector<bool> infected(n + 1);
- for (int i = 0; i < m; ++i) {
- int u;
- cin >> u;
- infected[u] = 1;
- }
- vector<vector<int>> adj(n + 1);
- for (int i = 0; i < n - 1; ++i) {
- int u, v;
- cin >> u >> v;
- adj[u].emplace_back(v);
- adj[v].emplace_back(u);
- }
- LCA lc(adj);
- vector<int> near_inf(n + 1, -1);
- auto dfs = [&](auto &self, int u, int p, int inf) -> void {
- if (infected[u])inf = u;
- near_inf[u] = inf;
- for (auto v: adj[u]) {
- if (v == p)continue;
- self(self, v, u, inf);
- }
- };
- dfs(dfs, 1, 0, -1);
- auto calc = [&](int u, int before, int after) -> int {
- if (u < 0) return 0;
- int tot = before + after + 1;
- int mx = min(before, after) + 1;
- assert(mx>0);
- int sum = pref_inc[mx];
- int l = tot - mx + 1;
- int r = tot;
- sum = add(sum, sub(pref_dec[r], pref_dec[l - 1]));
- sum = add(sum, mul(sub(pref[r], pref[l - 1]), sub(1 + tot, N)));
- r = l - 1; l = mx + 1;
- if (l <= r) {
- sum = add(sum, mul(mx, sub(pref[r], pref[l - 1])));
- }
- if (before == after) {
- sum = sub(sum, mul(mx, sub(pref[mx], pref[mx - 1])));
- }
- return sum;
- };
- while (q--) {
- int u, v, ans = 0;
- cin >> u >> v;
- if (u == v) {
- cout << (infected[u] ? 1 : 0) << '\n';
- continue;
- }
- int L = lc.get_LCA(u, v);
- vector<int> d;
- if (L == u || L == v) {
- if (L == v)swap(u, v);
- d.emplace_back(v);
- }
- else {
- d.emplace_back(u);
- d.emplace_back(v);
- }
- if(infected[L])
- ans = add(ans, calc(L, lc.get_distance(L,u),lc.get_distance(L,v)));
- for (auto x: d) {
- while (true) {
- x = near_inf[x];
- if (x == -1 || x==L || lc.get_LCA(x,L)!=L)break;
- ans = add(ans, calc(x, lc.get_distance(x,u),lc.get_distance(x,v)));
- x = lc.shifting(x, 1);
- }
- }
- cout<<ans<<'\n';
- }
- }
- void File() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
Advertisement
Add Comment
Please, Sign In to add comment