fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5. #define pb push_back
  6. #define MAX 100100
  7. #define LOG 17
  8.  
  9. int sum[(int)2e6], lc[(int)2e6], rc[(int)2e6];
  10.  
  11. int n,q;
  12. vector<tuple<int,int,int> > adj[MAX];
  13. int root[MAX], par[MAX][LOG+1], depth[MAX];
  14. int cur = 0;
  15. ll d[MAX];
  16.  
  17. int build(int l, int r)
  18. {
  19.     int pos = ++cur;
  20.     if(l == r){
  21.         sum[pos] = 0;
  22.         return pos;
  23.     }else{
  24.         int m = (l+r)>>1;
  25.         sum[pos] = 0;
  26.         lc[pos] = build(l,m);
  27.         rc[pos] = build(m+1,r);
  28.         return pos;
  29.     }
  30. }
  31.  
  32. int update(int l, int r, int po, int prev)
  33. {
  34.     int pos = ++cur;
  35.     if(l == r){
  36.         sum[pos] = sum[prev] + 1;
  37.         return pos;
  38.     }else{
  39.         int m = (l+r)>>1;
  40.         if(po <= m){
  41.             lc[pos] = update(l,m,po,lc[prev]);
  42.             rc[pos] = rc[prev];
  43.             sum[pos] = sum[lc[pos]] + sum[rc[pos]];
  44.         }else{
  45.             rc[pos] = update(m+1,r,po,rc[prev]);
  46.             lc[pos] = lc[prev];
  47.             sum[pos] = sum[lc[pos]] + sum[rc[pos]];
  48.         }
  49.         return pos;
  50.     }
  51. }
  52.  
  53. int get(int l, int r, int u, int v, int nodl, int nodr)
  54. {
  55.     if(r < u || v < l )return 0;
  56.     if(u <= l && r <= v) return sum[nodr] - sum[nodl];
  57.     int m = (l+r)>>1;
  58.     return get(l,m,u,v,lc[nodl],lc[nodr]) + get(m+1,r,u,v,rc[nodl],rc[nodr]);
  59. }
  60.  
  61. void nhap()
  62. {
  63.     cin >> n >> q;
  64.     for(int i = 0; i<n-1; i++){
  65.         int a,b,c,d; cin >> a >> b >> c >> d;
  66.         adj[a].pb(make_tuple(b,c,d));
  67.         adj[b].pb(make_tuple(a,c,d));
  68.     }
  69.     par[1][0] = 0;
  70.     depth[1] = 0;
  71.     root[0] = build(0,1e5);
  72.     root[1] = root[0];
  73.     d[1] = 0;
  74.     depth[0] = -1;
  75. }
  76.  
  77. void dfs(int v)
  78. {
  79.     for(tuple<int,int,int> u : adj[v]) if(get<0>(u) != par[v][0]){
  80.         int _u = get<0>(u);
  81.         depth[_u] = depth[v] + 1;
  82.         par[_u][0] = v;
  83.         root[_u] = update(0,1e5,get<2>(u),root[v]);
  84.         d[_u] = d[v] + get<1>(u);
  85.         dfs(_u);
  86.     }
  87. }
  88.  
  89. void pre_lca()
  90. {
  91.     for(int j = 1; j<=LOG; j++){
  92.         for(int i = 1; i<=n; i++) par[i][j] = par[par[i][j-1]][j-1];
  93.     }
  94. }
  95.  
  96. int lca(int u, int v)
  97. {
  98.     if(depth[u] < depth[v]) swap(u,v);
  99.     for(int i = LOG; i>=0; i--){
  100.         if(depth[par[u][i]] >= depth[v]) u = par[u][i];
  101.         if(u == v) return u;
  102.     }
  103.     for(int i = LOG; i>=0; i--){
  104.         if(par[u][i] != par[v][i]){
  105.             u = par[u][i];
  106.             v = par[v][i];
  107.         }
  108.     }
  109.     return par[u][0];
  110. }
  111.  
  112.  
  113.  
  114. void process()
  115. {
  116.     nhap();
  117.     dfs(1);
  118.     pre_lca();
  119.     while(q--){
  120.         int u,v,k,y; cin >> u >> v >> k >> y;
  121.         int a = lca(u,v);
  122.         int dem = depth[u] + depth[v] - 2*depth[a] - get(0,1e5,y,y,root[1],root[u]) - get(0,1e5,y,y,root[1],root[v]) + 2*get(0,1e5,y,y,root[1],root[a]);
  123.         if(dem <= k){
  124.             cout << d[u] + d[v] - 2*d[a] << '\n';
  125.         }else{
  126.             cout << -1 << '\n';
  127.         }
  128.     }
  129. }
  130.  
  131. signed main()
  132. {
  133.     ios_base::sync_with_stdio(0); cin.tie(0);
  134.     process();
  135.     return 0;
  136. }
  137.  
Success #stdin #stdout 0.01s 11668KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WSsaTQ
language:
C++ (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!