fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i)&1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 200005
  7. #define fi first
  8. #define se second
  9. #define int long long
  10.  
  11. using namespace std;
  12.  
  13. int sz[maxn],A,B,n;
  14. int resall=0;
  15. vector<pair<int,int>> vecall,vecin;
  16. struct adja{
  17.     int v,w,c;
  18. };
  19. vector<adja> adj[maxn];
  20. bool banned[maxn];
  21.  
  22. struct Fenwick{
  23.     int n;
  24.     vector<int> st;
  25.     Fenwick(int _n=0){
  26.         n=_n;
  27.         st.assign(n+5,0);
  28.     }
  29.     void update(int pos,int val){
  30.         for(;pos<=n;pos+=pos&-pos) st[pos]+=val;
  31.     }
  32.     int get(int pos){
  33.         int res=0;
  34.         for(;pos>0;pos-=pos&-pos) res+=st[pos];
  35.         return res;
  36.     }
  37.     void reset(int _n=0){
  38.         n=_n;
  39.         fill(st.begin(),st.begin()+n+5,0);
  40.     }
  41. };
  42.  
  43. Fenwick tree(200005);
  44.  
  45. void countChild(int u,int p){
  46.     sz[u]=1;
  47.     for(auto [v,w,c]:adj[u]){
  48.         if(v!=p&&!banned[v]){
  49.             countChild(v,u);
  50.             sz[u]+=sz[v];
  51.         }
  52.     }
  53. }
  54.  
  55. int find_centroid(int u,int p,int S){
  56.     for(auto [v,w,c]:adj[u]){
  57.         if(v!=p&&!banned[v]&&sz[v]>S/2){
  58.             return find_centroid(v,u,S);
  59.         }
  60.     }
  61.     return u;
  62. }
  63.  
  64. void dfs(int u,int p,int L,int T){
  65.     vecin.push_back({L,T});
  66.     for(auto [v,w,c]:adj[u]){
  67.         if(v!=p&&!banned[v]) dfs(v,u,L+w,T+c);
  68.     }
  69. }
  70.  
  71. int calc(vector<pair<int,int>>&vec,int limitL,int limitT){
  72.     if(vec.size()<2) return 0;
  73.     vector<int> comp;
  74.     for(auto [L,W]:vec) comp.push_back(W);
  75.     sort(comp.begin(),comp.end());
  76.     comp.erase(unique(comp.begin(),comp.end()),comp.end());
  77.     sort(vec.begin(),vec.end());
  78.     tree.reset(comp.size());
  79.     int res=0,ptr=0,self=0,m=vec.size();
  80.     for(int i=m-1;i>=0;i--){
  81.         while(ptr<m&&vec[i].fi+vec[ptr].fi<=limitL){
  82.             int pos=lower_bound(comp.begin(),comp.end(),vec[ptr].se)-comp.begin()+1;
  83.             tree.update(pos,1);
  84.             ptr++;
  85.         }
  86.         int pos=upper_bound(comp.begin(),comp.end(),limitT-vec[i].se)-comp.begin();
  87.         res+=tree.get(pos);
  88.         if(2*vec[i].fi<=limitL&&2*vec[i].se<=limitT) self++;
  89.     }
  90.     return (res-self)/2;
  91. }
  92.  
  93. void solve(int u){
  94.     countChild(u,0);
  95.     u=find_centroid(u,0,sz[u]);
  96.     vecall.clear();
  97.     vecall.push_back({0,0});
  98.     for(auto [v,w,c]:adj[u]){
  99.         if(banned[v]) continue;
  100.         vecin.clear();
  101.         dfs(v,u,w,c);
  102.         for(auto p:vecin) vecall.push_back(p);
  103.         resall-=calc(vecin,A,B);
  104.     }
  105.     resall+=calc(vecall,A,B);
  106.     banned[u]=1;
  107.     for(auto [v,w,c]:adj[u]){
  108.         if(!banned[v]) solve(v);
  109.     }
  110. }
  111.  
  112. signed main(){
  113.     itachi
  114.     freopen("BRT.inp","r",stdin);
  115.     freopen("BRT.out","w",stdout);
  116.     cin>>n>>A>>B;
  117.     for(int i=1;i<n;i++){
  118.         int u,v,w,c;
  119.         cin>>u>>v>>w>>c;
  120.         adj[u].push_back({v,w,c});
  121.         adj[v].push_back({u,w,c});
  122.     }
  123.     solve(1);
  124.     cout<<resall;
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 9876KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/6iJj7x
language:
C++14 (gcc 8.3)
created:
1 day 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!