fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define bye return
  5. #define yes "YES"
  6. #define no "NO"
  7. #define Shoyo ios_base::sync_with_stdio(0);cin.tie(NULL);
  8. #define el "\n"
  9. const ll Log=18, N=1e6;
  10. ll ans[N][Log],mx[N][Log],dist[N];
  11. ll level[N]={0};
  12. vector<vector<ll>> adj;
  13. void dfs(ll u,ll p) {//nlogn
  14.     ans[u][0]=p;
  15.     level[u]=level[p]+1;
  16.     for (ll i=1;i<Log;i++) {
  17.         ll dad=ans[u][i-1];
  18.         mx[u][i]=max(mx[u][i-1],mx[dad][i-1]);
  19.         ans[u][i]=ans[dad][i-1];
  20.     }
  21.     for (auto v:adj[u]) {
  22.         if (v!=p) {
  23.             dfs(v,u);
  24.         }
  25.     }
  26. }
  27. ll kth(ll u,ll k) {//logn
  28.     for (ll i=0;i<Log;i++) {
  29.         if ((k>>i)&1) {
  30.             u=ans[u][i];
  31.         }
  32.     }
  33.     return u;
  34. }
  35. ll LCA(ll u,ll v) {//logn
  36.     if (level[u]<level[v]) swap(u,v);
  37.     u=kth(u,level[u]-level[v]);
  38.     if (u==v) return u;
  39.     for (ll i=Log-1;i>=0;i--) {
  40.         if (ans[u][i] != ans[v][i]) {
  41.             u=ans[u][i];
  42.             v=ans[v][i];
  43.         }
  44.     }
  45.     return ans[u][0];
  46. }
  47. void solve() {
  48. ll n,a,b;cin>>n>>a>>b;
  49.     adj.assign(n+1,{});
  50.     for (ll i=1;i<n;i++) {
  51.         ll x,y;cin>>x>>y;
  52.         adj[x].push_back(y);
  53.         adj[y].push_back(x);
  54.     }
  55.     dfs(a,0);
  56.     map<ll,ll>mp;
  57.     for (ll i=1;i<=n;i++) {
  58.         mp[LCA(i,b)]++;
  59.     }
  60.   //  for (auto [a,b]:mp)cout<<a<<" "<<b<<endl;
  61.  
  62. }
  63. int main(){
  64.     Shoyo;
  65.     ll t = 1;
  66.     if(!(cin >> t)) return 0;
  67.     while (t--) {
  68.         solve();
  69.     }
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/PCOWzs
language:
C++14 (gcc 8.3)
created:
4 days 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!