fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. long long T,n,m,k,p=1e9+7,new_p=1e9+9;
  4. int dx[]={-1,1,0,0};
  5. int dy[]={0,0,-1,1};
  6. vector<long long>visited(1e6),Depth(1e6,0);
  7. void topological_sort(int x,vector<vector<long long>>&a,vector<long long>&ans){
  8.                 if(visited[x])return ;
  9.                 visited[x]=1;
  10.                 for(auto i:a[x]){
  11.                     topological_sort(i,a,ans);
  12.                 }
  13.                 ans.push_back(x);
  14.                 return;
  15.  }
  16. void dfs(int x,vector<vector<long long>>&a,vector<vector<long long>>&lca_of,long long depth,long long par){
  17.                 Depth[x]=depth;
  18.                 lca_of[x][0]=par;
  19.                 for(int i=1;i<30;i++)lca_of[x][i]=lca_of[lca_of[x][i-1]][i-1];
  20.                 for(auto i:a[x]){
  21.                     dfs(i,a,lca_of,depth+1,x);
  22.                 }
  23.                 return;
  24.     }
  25. long long power(long long a,long long b,long long p){
  26.                 if(b==0)return 1;
  27.                 long long res=power(a,b/2,p);
  28.                 if(b%2){res=(res*res)%p;return (res*a)%p;}
  29.                 return (res*res)%p;
  30.  }
  31. long long gcd(long long a,long long b){
  32.                             if(b==0)return a;
  33.                             return gcd(b,a%b);
  34.  }
  35. long long lcm(long long a,long long b){
  36.                     return abs(a*b)/gcd(a,b);
  37. }
  38. long long lc(long long x,long long y,vector<vector<long long>>&lca_of){
  39.                 if(Depth[x]>Depth[y]){
  40.                     swap(x,y);
  41.                 }
  42.                 while(Depth[x]!=Depth[y]){
  43.                     for(int i=1;i<30;i++){
  44.                         if(lca_of[x][i]==lca_of[y][i]){
  45.                             y=lca_of[y][i-1];
  46.                             break;
  47.                         }
  48.                     }
  49.                 }
  50.                 while(x!=y){
  51.                     for(int i=1;i<30;i++){
  52.                         if(lca_of[x][i]==lca_of[y][i]){
  53.                             y=lca_of[y][i-1];
  54.                             x=lca_of[x][i-1];
  55.                             break;
  56.                         }
  57.                     }
  58.                 }
  59.                 return x;
  60. }
  61. int main(){
  62.      ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  63.                                    // freopen("zeros.in", "r", stdin);
  64.                                   //  freopen(".out", "w", stdout);
  65.                                           T=1;
  66.                                           cin>>T;
  67.                                           vector<long long>fact(2e5+3),invers(2e5+3);
  68.                                           invers[0]=fact[0]=invers[1]=fact[1]=1;
  69.                                           for(long long i=2;i<=2e5;i++){
  70.                                             fact[i]=i*fact[i-1];
  71.                                             fact[i]%=p;
  72.                                             invers[i]=power(fact[i],p-2,p);
  73.                                           }
  74. cout << fact[100000];
  75. return 0;
  76.                                         while(T--){
  77.                                             cin>>n;
  78.                                             vector<vector<long long>>a(n+1),lca_of(n+1,vector<long long>(30,1));
  79.                                             for(int i=1;i<n;i++){
  80.                                                 long long u,v;
  81.                                                 cin>>u>>v;
  82.                                                 a[u].push_back(v);
  83.                                             }
  84.                                             dfs(1,a,lca_of,0,1);
  85.                                         cin>>m;
  86.                                         while(m--){
  87.                                             long long u,v;
  88.                                             cin>>u>>v;
  89.                                             long long lca=lc(u,v,lca_of);
  90.                                             long long ans1=Depth[u]-Depth[lca];
  91.                                             long long ans2=Depth[v]-Depth[lca];
  92.                                             long long ans=fact[ans1+ans2];
  93.                                             ans*=invers[ans1];
  94.                                             ans%=p;
  95.                                             ans*=invers[ans2];
  96.                                             ans%=p;
  97.                                             cout<<ans<<'\n';
  98.  
  99.                                         }
  100.                                         }
  101.  
  102.                                         return 0;
  103. }
  104. /*
  105. 2
  106. 6
  107. 1 2
  108. 1 3
  109. 2 4
  110. 2 5
  111. 3 6
  112. 5
  113. 1 2
  114. 2 3
  115. 3 4
  116. 4 5
  117. 5 6
  118. 2
  119. 1 2
  120. 1
  121. 1 2
  122. */
  123.  
Success #stdin #stdout 0.17s 22116KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
457992974
https://ideone.com/ZJH58m
language:
C++14 (gcc 8.3)
created:
1 year 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!