fork download
copy 
  1. /*
  2.     STAY ORGANIZED
  3.     CHANGE YOUR APPROACH
  4. */
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll ;
  8. typedef long double ld ;
  9. #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
  10. #define pb push_back
  11. #define pi pair<ll,ll>
  12. #define pll pair<ll,ll>
  13. #define yes cout<<"Yes"<<endl;
  14. #define no cout<<"No"<<endl;
  15. #define flag cout<<"hi"<<endl;
  16. #define fr(i,a,b) for(ll i = a;i < (ll)b;i++)
  17. #define rfr(i,a,b) for(ll i = a;i > (ll)b;i--)
  18. #define F first
  19. #define S second
  20. #define all(x) (x).begin(), (x).end()
  21. #define alll(x) ((x).begin()+1), (x).end()
  22. #define MOD mod
  23. #define endl '\n'
  24. const ll mod = 1e9+7 ;
  25. void io(){ios::sync_with_stdio(false) ;cin.tie(NULL) ;freopen("awesome.in","r",stdin) ;//freopen("problem1.out","w",stdout) ;
  26. }
  27. void dbg(vector<ll> tab){for(auto it : tab) cout<<it<<" ";cout<<endl;}
  28. void dbgg(pi p){cout<<p.F<<" "<<p.S<<endl;}
  29. void dbgpi(vector<pi> tab){for(auto it : tab) dbgg(it) ;}
  30. template<class T> bool ckmax(T& a, const T& b){return a < b ? a = b, 1 : 0;}
  31. template<class T> bool ckmin(T& a, const T& b){return a > b ? a = b, 1 : 0;}
  32. template<class T> void add(T& a, const T& b){a = a + b ; if(a>mod) a-= mod ;}
  33. void nop(){cout<<-1<<endl;return;}
  34. #define forr(i, x, y)   for(ll i = x; i <= y; i++)
  35. const ll inf = 1e9 +1;
  36. const ll N = 2e5+5 , MAXN = 1e5+5  , NAX = 1001 ;
  37.  
  38. ll n , L , R ;
  39. vector<ll> v[N] ;
  40. ll sz[N] , dep[N] ;
  41.  
  42.  
  43. ll ans = 0 ;
  44. template<class T> struct Seg { // comb(ID,b) = b
  45. 	const T ID = 0; T comb(T a, T b) { return a+b; }
  46. 	ll n; vector<T> seg;
  47. 	void init(ll _n) { n = _n; seg.assign(2*n,ID); }
  48. 	void pull(ll p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
  49. 	void upd(ll p, T val) { // set val at position p
  50. 		seg[p += n] += val; for (p /= 2; p; p /= 2) pull(p); }
  51. 	T query(ll l, ll r) {	// sum on llerval [l, r]
  52. 	    ckmin(l,n+1) ; ckmin(r,n+1) ;
  53. 		T ra = ID, rb = ID;
  54. 		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
  55. 			if (l&1) ra = comb(ra,seg[l++]);
  56. 			if (r&1) rb = comb(seg[--r],rb);
  57. 		}
  58. 		return comb(ra,rb);
  59. 	}
  60. };
  61.  
  62. Seg<ll> st ;
  63.  
  64.  
  65. void dfs(ll node = 1 , ll oj = 1)
  66. {
  67.     dep[node] = dep[oj]+1 ;
  68.     sz[node] = 1 ;
  69.     for(auto it : v[node]){
  70.         if(it==oj) continue ;
  71.         dfs(it,node) ;
  72.         sz[node] += sz[it] ;
  73.     }
  74. }
  75.  
  76. void cnt(ll node , ll oj , ll d , ll qu , ll curr)
  77. {
  78. //    cout<<node<<" "<<st.query(max(0LL,L-d + dep[curr]) , max(0LL,R-d+dep[curr]))<<endl;
  79.     if(qu) ans += st.query(max(0LL,L-d + dep[curr]) , max(0LL,R-d+dep[curr])) ;
  80.     else st.upd(dep[node] , 1) ;
  81.     for(auto i : v[node]){
  82.         if(i==oj) continue ;
  83.         cnt(i,node,d+1 ,qu,curr) ;
  84.     }
  85. }
  86.  
  87. void rem(int node , int oj)
  88. {
  89.     st.upd(dep[node] , -1) ;
  90.     for(auto it : v[node]){
  91.         if(it!=oj) rem(it,node) ;
  92.     }
  93. }
  94.  
  95. void work(ll node , ll oj , int big)
  96. {
  97.     ll b_sz = 0 , b = -1 ;
  98.     for(auto it : v[node]){
  99.         if(it==oj) continue ;
  100.         if(ckmax(b_sz , sz[it])) b = it ;
  101.     }
  102.     for(auto it : v[node]){
  103.         if(it!=oj && it!=b) work(it,node,0) ;
  104.     }
  105.     if(b>0) work(b,node,1) ;
  106.     for(auto it : v[node]){
  107.         if(it!=b && it!=oj){
  108.             cnt(it,node,1,1,node) ;
  109.             cnt(it,node,1,0,node) ;
  110.         }
  111.     }
  112.     ans += st.query(min(n+1,L+dep[node]) , min(n+1,R+dep[node])) ;
  113.     st.upd(dep[node] , 1) ;
  114.     if(!big){
  115.         rem(node,oj) ;
  116.     }
  117.  
  118. }
  119.  
  120.  
  121. void solve()
  122. {
  123.     ll l , r ;
  124.     cin>>n>>l>>r ;
  125.     for(ll i = 0 ; i<=n ; i++){
  126.         v[i].clear() ;
  127.         dep[i] = sz[i] =  0 ;
  128.     }
  129.     ans = 0 ;
  130.     L = n - (r+1) , R = n - (l+1) ;
  131.     for(ll i = 1 ; i<n ; i++){
  132.         ll x , y ;
  133.         cin>>x>>y ;
  134.         v[x].pb(y) ;
  135.         v[y].pb(x) ;
  136.     }
  137.     st.init(n+3) ;
  138.     dfs() ;
  139.     work(1,1,1) ;
  140.     cout<<ans<<endl;
  141.  
  142.  
  143. }
  144.  
  145.  int main()
  146. {
  147.     io() ;
  148.     srand(time(0)) ;
  149.     ll tt = 1 ;
  150.     cin>>tt ;
  151.     for(ll i = 1 ; i<=tt ; i++){
  152.         solve() ;
  153.     }
  154. }
Success #stdin #stdout 0.01s 10452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/NW94ux
language:
C++ (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!