fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(v) v.begin(),v.end()
  4. #define MASK(i) (1LL << (i))
  5. #define ii pair<int,int>
  6. #define fi first
  7. #define se second
  8. #define endl '\n'
  9. #define forr(i,l,r,add) for(int i = l;i <= r; i = i + add)
  10. #define fodd(i,l,r,sub) for(int i = l;i >= r ; i = i - sub)
  11. template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
  12. template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
  13.  
  14. using namespace std;
  15.  
  16. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  17. #define rand rd
  18.  
  19. long long Rand(long long l , long long h){
  20. 	assert(l <= h);
  21. 	return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
  22. }
  23.  
  24.  
  25. //////////////////////////////////////////////////////////// end of template ////////////////////////////////////////////////////////////
  26.  
  27. const int MAX = 4e5 + 5 , MOD = 1e9 + 7;
  28. int n , q;
  29. vector <int> edge[MAX];
  30. int st[MAX] , en[MAX] , cnt_eleur , val_dinh[MAX];
  31. int RMQ[MAX][20] , cnt_RMQ , in[MAX];
  32. int P[MAX];
  33. int H[MAX];
  34. int par[MAX];
  35. int POW[50];
  36. bool ok[MAX];
  37.  
  38. void dfs(int u){
  39.     H[u] = H[par[u]] + 1;
  40.     st[u] = ++cnt_eleur;
  41.     val_dinh[st[u]] = u;
  42.     RMQ[++cnt_RMQ][0] = cnt_eleur;
  43.     in[cnt_eleur] = cnt_RMQ;
  44.     for(auto x : edge[u]) if(x != par[u]){
  45.         par[x] = u;
  46.         dfs(x);
  47.         RMQ[++cnt_RMQ][0] = st[u];
  48.     }
  49.     en[u] = cnt_eleur;
  50. }
  51.  
  52. void build_RMQ(){
  53.     dfs(1);
  54.     POW[0] = 1;
  55.     forr(j , 1 , 20 , 1){
  56.         POW[j] = POW[j - 1] * 2;
  57.         if(POW[j] > 2 * n) break;
  58.         P[POW[j]] = j;
  59.         forr(i , 1 , cnt_RMQ - POW[j] + 1 , 1) RMQ[i][j] = min(RMQ[i][j - 1] , RMQ[i + POW[j - 1]][j - 1]);
  60.     }
  61.     forr(i , 1 , 2 * n , 1) maximize(P[i] , P[i - 1]);
  62. }
  63.  
  64. int num , dinh[MAX];
  65.  
  66. int GET_LCA(int x , int y){
  67.     x = in[st[x]] , y = in[st[y]];
  68.     if(x > y) swap(x , y);
  69.     int cl = y - x + 1;
  70.     //cout << " HOW " << x << ' ' << y << endl << min(RMQ[x][P[cl]] , RMQ[y - POW[P[cl]] + 1][P[cl]]) << endl;
  71.     return val_dinh[min(RMQ[x][P[cl]] , RMQ[y - POW[P[cl]] + 1][P[cl]])];
  72. }
  73.  
  74. bool check(int x , int y){
  75.     return st[x] < st[y];
  76. }
  77.  
  78. vector <ii> adj[MAX];
  79. ii dp[MAX] , dp2[MAX];
  80.  
  81. void add(int &x , int y){
  82.     x = x + y;
  83.     if(x >= MOD) x = x - MOD;
  84. }
  85.  
  86. void sub(int &x , int y){
  87.     x = x - y;
  88.     if(x < 0) x = x + MOD;
  89. }
  90.  
  91. int res = 0;
  92.  
  93. void dfs_dp1(int u){
  94.     dp[u] = {0 , 0};
  95.     for(auto x : adj[u]){
  96.         dfs_dp1(x.fi);
  97.         add(dp[u].fi , dp[x.fi].fi);
  98.         dp[u].se = (dp[u].se + dp[x.fi].se + 1ll * dp[x.fi].fi * x.se) % MOD;
  99.     }
  100.     if(ok[u]) add(dp[u].fi , u) , res = (res + 1ll * u * dp[u].se) % MOD;
  101. }
  102.  
  103. void dfs_dp2(int u){
  104.     if(ok[u]) res = (res + u * 1ll * dp2[u].se) % MOD;
  105.     //cout << u << ' ' << dp2[u].fi << ' ' << dp2[u].se << endl;
  106.     add(dp2[u].fi , dp[u].fi) , add(dp2[u].se , dp[u].se);
  107.     for(auto x : adj[u]){
  108.         dp2[x.fi] = dp2[u];
  109.         sub(dp2[x.fi].fi , dp[x.fi].fi);
  110.         sub(dp2[x.fi].se , dp[x.fi].se);
  111.         add(dp2[x.fi].se , 1ll * dp2[x.fi].fi * x.se % MOD);
  112.         sub(dp2[x.fi].se , 1ll * dp[x.fi].fi * x.se % MOD);
  113.         dfs_dp2(x.fi);
  114.     }
  115. }
  116.  
  117. void query(){
  118.     res = 0;
  119.     cin >> num;
  120.     forr(i , 1 , num , 1){
  121.         cin >> dinh[i];
  122.     }
  123.     sort(dinh + 1 , dinh + 1 + num , check);
  124.     dinh[num + 1] = dinh[1];
  125.     vector <int> save;
  126.     forr(i , 1 , num , 1){
  127.         save.push_back(dinh[i]);
  128.         save.push_back(GET_LCA(dinh[i] , dinh[i + 1]));
  129.         //cout << dinh[i] << ' ' << dinh[i + 1] << ' ' << GET_LCA(dinh[i] , dinh[i + 1]) << endl;
  130.     }
  131.     sort(all(save) , check);
  132.     save.resize(unique(all(save)) - save.begin());
  133.     for(auto &x : save){
  134.         adj[x].clear();
  135.         ok[x] = 0;
  136.         //cout << x << ' ';
  137.         //cout << st[x] << endl;
  138.     }
  139.     forr(i , 1 , num , 1){
  140.         ok[dinh[i]] = 1;
  141.         //cout << dinh[i] << ' ' << endl;
  142.     }
  143.     stack <int> sta;
  144.     sta.push(save[0]);
  145.     forr(i , 1 , (int)save.size() - 1 , 1){
  146.         int x = save[i];
  147.         //cout << sta.size() << endl;
  148.         while(st[x] > en[sta.top()]) sta.pop();
  149.         //cout << i << ' ' << sta.size() << endl;
  150.         adj[sta.top()].push_back({x , -H[sta.top()] + H[x]});
  151.         //cout << sta.top() << ' ' << x << ' ' << -H[sta.top()] + H[x] << endl;
  152.         sta.push(x);
  153.     }
  154.     dfs_dp1(save[0]);
  155.     dp2[save[0]] = {0 , 0};
  156.     //cout << res << endl;
  157.     //forr(i , 1 , 3 , 1) cout << dp[i].fi << ' ' << dp[i].se << endl;
  158.     dfs_dp2(save[0]);
  159.     //cout << res << endl;
  160.     //forr(i , 1 , 3 , 1) cout << dp2[i].fi << ' ' << dp2[i].se << endl;
  161.     cout << (1ll * res * 500000004) % MOD << endl;
  162. }
  163.  
  164. void INP(){
  165.     cin >> n >> q;
  166.     forr(i , 1 , n - 1 , 1){
  167.         int x , y;
  168.         cin >> x >> y;
  169.         edge[x].push_back(y);
  170.         edge[y].push_back(x);
  171.     }
  172.     build_RMQ();
  173.     while(q--){
  174.         query();
  175.     }
  176. }
  177.  
  178. int main()
  179. {
  180.     ios_base::sync_with_stdio(false);
  181.     cin.tie(0);
  182.     cout.tie(0);
  183.     #define TASK "file"
  184.     //freopen(TASK".inp" , "r" , stdin);
  185.     //freopen(TASK".out" , "w" , stdout);
  186.     INP();
  187.     return 0;
  188. }
  189.  
Success #stdin #stdout 0.01s 28008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qtCLQj
language:
C++14 (clang 8.0)
created:
16 hours 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!