fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4. #define ff first
  5. #define ss second
  6. #define pb push_back
  7. #define po pop_back()
  8. #define lb lower_bound
  9. #define ub upper_bound
  10. #define nl "\n"
  11. #define dbg(x) cout << (#x) << " = " << (x) << nl
  12. #define fl(i,a,b,c) for(int i=a;i<b;i+=c)
  13. #define rl(i,a,b,c) for(int i=a;i>b;i-=c)
  14. #define sn(a,l) fl(i,0,l,1) cin >> a[i]
  15. #define pr(a,l) fl(i,0,l,1) cout << a[i] << ' '
  16. #define all(a) a.begin(),a.end()
  17. #define test() int ts; cin>>ts; while(ts--)
  18. const int INF = 1e9 + 1;
  19. const ll MOD = 1e9 + 7;
  20. const int N = 1e5 + 5;
  21. const int K = 20;
  22. const int B = 30;
  23. using namespace std;
  24.  
  25. // #include <ext/pb_ds/assoc_container.hpp> 
  26. // #include <ext/pb_ds/tree_policy.hpp> 
  27. // using namespace __gnu_pbds; 
  28. // template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  29.  
  30. // CODE BEGINS HERE --- TREES
  31.  
  32. int n;
  33. vector<int> lst[N];
  34. int LCA[N][K], dp[N][B];
  35. int a[N], dis[N];
  36. ll info[B], fc[N], ifc[N];
  37.  
  38. ll power(ll b, ll p)
  39. {
  40. 	ll r = 1;
  41. 	while(p > 0)
  42. 	{
  43. 		if(p & 1)
  44. 			r = (r * b) % MOD;
  45. 		b = (b * b) % MOD;
  46. 		p >>= 1;
  47. 	}
  48. 	return r % MOD;
  49. }
  50.  
  51. void reset()
  52. {
  53.     fc[0] = ifc[0] = 1;
  54.     fl(i,0,n,1)
  55.     {
  56.         fc[i+1] = ((i+1) * 1LL * fc[i]) % MOD;
  57.         ifc[i+1] = power(fc[i+1], MOD-2) % MOD;
  58.         fl(j,0,K,1)
  59.             LCA[i][j] = -1;
  60.         fl(j,0,B,1)
  61.             dp[i][j] = 0;
  62.     }
  63. }
  64.  
  65. void dfs(int u=0, int p=-1, int d=0)
  66. {
  67.     LCA[u][0] = p;
  68.     dis[u] = d;
  69.     fl(j,1,K,1)
  70.         if(LCA[u][j-1] != -1)
  71.             LCA[u][j] = LCA[LCA[u][j-1]][j-1];
  72.     fl(j,0,B,1)
  73.         if(a[u] & (1<<j))
  74.             dp[u][j]++;
  75.     for(auto v : lst[u])
  76.         if(v != p)
  77.         {
  78.             fl(j,0,B,1)
  79.                 dp[v][j] += dp[u][j];
  80.             dfs(v,u,d+1);
  81.         }
  82. }
  83.  
  84. int getLCA(int a, int b)
  85. {
  86.     if(dis[b] < dis[a])
  87.         swap(a,b);
  88.     int d = dis[b] - dis[a];
  89.     while(d > 0)
  90.     {
  91.         int l = (int)log2(d);
  92.         b = LCA[b][l];
  93.         d -= (1<<l);
  94.     }
  95.     if(a == b)
  96.         return a;
  97.     rl(i,K-1,-1,1)
  98.         if(LCA[a][i] != -1 && (LCA[a][i] != LCA[b][i]))
  99.         {
  100.             a = LCA[a][i];
  101.             b = LCA[b][i];
  102.         }
  103.     return LCA[a][0];
  104. }
  105.  
  106. void getArray(int x, int y, int lca)
  107. {
  108.     fl(j,0,B,1)
  109.         info[j] = dp[x][j] + dp[y][j] - 2*dp[lca][j] + ((a[lca] & (1<<j)) ? 1 : 0);
  110. }
  111.  
  112. int getDistance(int x, int y, int lca)
  113. {
  114.     return (dis[x] + dis[y] - 2*dis[lca]);
  115. }
  116.  
  117. ll mCr(int m, int r)
  118. {
  119.     if(m < r)
  120.         return 0;
  121.     return (fc[m] * ((ifc[r] * ifc[m-r]) % MOD)) % MOD;
  122. }
  123.  
  124. ll query_1(int d)
  125. {
  126.     ll ans = 0;
  127.     fl(j,0,B,1)
  128.     	ans = (ans + ((1LL<<j) * info[j])) % MOD;
  129.     return ans % MOD;
  130. }
  131.  
  132. ll query_2(int d)
  133. {
  134.     ll ans = 0;
  135.     fl(j,0,B,1)
  136.     {
  137.         int z = d - info[j];
  138.         // ans = (ans + ((1LL<<j)*(mCr(o,2) + mCr(o,1)*mCr(z,1))%MOD)%MOD) % MOD;
  139.         ans = (ans + ((1LL<<j)*((mCr(d,2) - mCr(z,2) + MOD) % MOD)) % MOD) % MOD;
  140.     }
  141.     return ans % MOD;
  142. }
  143.  
  144. ll query_3(int d)
  145. {
  146.     ll ans = 0;
  147.     fl(j,0,B,1)
  148.     {
  149.         int z = d - info[j];
  150.         ans = (ans + ((1LL<<j)*((mCr(d,3) - mCr(z,3) + MOD) % MOD)) % MOD) % MOD;
  151.     }
  152.     return ans % MOD;
  153. }
  154.  
  155. ll query_4(int d)
  156. {
  157.     ll ans = 0;
  158.     fl(j,0,B,1)
  159.     {
  160.         int z = d - info[j];
  161.         ans = (ans + ((1LL<<j)*((mCr(d,4) - mCr(z,4) + MOD) % MOD)) % MOD) % MOD;
  162.     }
  163.     return ans % MOD;
  164. }
  165.  
  166. void solve()
  167. {
  168.     cin >> n;
  169.     sn(a,n);
  170.  
  171.     reset();
  172.  
  173.     fl(i,1,n,1)
  174.     {
  175.         int u, v;
  176.         cin >> u >> v;
  177.         lst[--u].pb(--v);
  178.         lst[v].pb(u); // undirected graph
  179.     }
  180.  
  181.     dfs();
  182.  
  183.     test()
  184.     {
  185.         int t, u, v, l, d;
  186.         cin >> t >> u >> v;
  187.         --u, --v;
  188.         l = getLCA(u,v);
  189.         getArray(u,v,l);
  190.         d = (getDistance(u,v,l) + 1);
  191.         if(t == 1)
  192.             cout << query_1(d) << nl;
  193.         else if(t == 2)
  194.             cout << query_2(d) << nl;
  195.         else if(t == 3)
  196.             cout << query_3(d) << nl;
  197.         else
  198.             cout << query_4(d) << nl;
  199.     }
  200.  
  201. }
  202.  
  203. int main()
  204. {
  205.     fastIO
  206.     solve();
  207.     return 0;
  208. }
Success #stdin #stdout 0s 5868KB
comments (?)
stdin
copy 
4
24 62 56 12
1 2
1 3
3 4
12
1 1 2
1 1 3
1 1 4
1 2 3
1 2 4
1 3 4
2 1 2
2 1 3
2 1 4
2 2 3
2 2 4
2 3 4
stdout
copy 
86
80
92
142
154
68
62
56
144
180
330
60
https://ideone.com/9pMHiu
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!