fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll           long long
  5. #define pii          pair<ll,ll>
  6. #define bug(a)       cerr << #a << " : " << a << endl;
  7. #define FastRead     ios_base::sync_with_stdio(false);cin.tie(NULL);
  8.  
  9. const ll MAX = 1e5+10;
  10.  
  11. vector<ll>adj[MAX] , ans[MAX] , cnt[MAX] , subb[MAX];
  12. ll n , dep[MAX] , T[MAX] , P[MAX][30] , cum[MAX][30] , root;
  13. map<pii,ll>cost;
  14.  
  15. void DFS(ll src,ll par,ll lev)
  16. {
  17.     dep[src] = lev;
  18.     T[src] = par;
  19.  
  20.     for(ll i=0;i<adj[src].size();i++)
  21.     {
  22.         ll x = adj[src][i];
  23.  
  24.         if(x == par)
  25.             continue;
  26.         cum[x][0] = cost[{src,x}];
  27.         DFS(x,src,lev+1);
  28.     }
  29. }
  30. void initLCA()
  31. {
  32.     memset(P,-1,sizeof P);
  33.  
  34.     for(ll i=1;i<=n;i++)
  35.         P[i][0] = T[i];
  36.     for(ll j=1; 1<<j <n;j++)
  37.     {
  38.         for(ll i=1;i<=n;i++)
  39.         {
  40.             if(P[i][j-1] != -1)
  41.             {
  42.                 P[i][j] = P[P[i][j-1]][j-1];
  43.                 cum[i][j] = cum[i][j-1] + cum[P[i][j-1]][j-1];
  44.             }
  45.         }
  46.     }
  47. }
  48. ll lca_query(ll u,ll v)
  49. {
  50.     if(dep[u] < dep[v])
  51.         swap(u,v);
  52.  
  53.     ll log = log2(dep[u]);
  54.     ll sum = 0;
  55.     for(ll i=log;i>=0;i--)
  56.     {
  57.         if(dep[u]-(1<<i) >= dep[v])
  58.         {
  59.             sum += cum[u][i];
  60.             u = P[u][i];
  61.         }
  62.     }
  63.     if(u == v)
  64.         return sum;
  65.     for(ll i=log;i>=0;i--)
  66.     {
  67.         if(P[u][i] != -1 && P[u][i] != P[v][i])
  68.         {
  69.             sum += cum[u][i]+cum[v][i];
  70.             u = P[u][i];
  71.             v = P[v][i];
  72.         }
  73.     }
  74.     return sum + cum[u][0] + cum[v][0];
  75. }
  76. ll dist(ll u,ll v)
  77. {
  78.     return lca_query(u,v);
  79. }
  80. struct CentroidDecomposition
  81. {
  82.     ll path[MAX] , sub[MAX];
  83.     bool vis[MAX];
  84.  
  85.     CentroidDecomposition()
  86.     {
  87.         memset(vis,0,sizeof vis);
  88.         memset(path,0,sizeof path);
  89.     }
  90.  
  91.     void subDFS(ll src,ll par)
  92.     {
  93.         sub[src] = 1;
  94.  
  95.         for(auto i : adj[src])
  96.         {
  97.             if(i == par || vis[i])
  98.                 continue;
  99.  
  100.             subDFS(i,src);
  101.             sub[src] += sub[i];
  102.         }
  103.     }
  104.     ll centroid(ll src,ll par,ll sz)
  105.     {
  106.         for(auto i : adj[src])
  107.         {
  108.             if(i == par || vis[i])
  109.                 continue;
  110.             else if(sub[i] > sz)
  111.                 return centroid(i,src,sz);
  112.         }
  113.         return src;
  114.     }
  115.     ll decompose(ll src,ll par)
  116.     {
  117.         subDFS(src,-1);
  118.         ll c = centroid(src,-1,sub[src]/2);
  119.         vis[c] = 1;
  120.         path[c] = par;
  121.  
  122.         for(auto i : adj[c])
  123.         {
  124.             if(!vis[i])
  125.             {
  126.                 ll child = decompose(i,c);
  127.                 for(auto j : subb[child])
  128.                     subb[c].push_back(j);
  129.             }
  130.         }
  131.         subb[c].push_back(c);
  132.         for(auto i : subb[c])
  133.         {
  134.             ans[c].push_back(dist(c,i));
  135.             if(par != -1)
  136.                 cnt[c].push_back(dist(par,i));
  137.         }
  138.         return c;
  139.     }
  140. } tree;
  141.  
  142. struct QueryHandler
  143. {
  144.     ll query(ll u,ll l)
  145.     {
  146.         ll cur = u;
  147.         ll ret = upper_bound(ans[u].begin(),ans[u].end(),l)-ans[u].begin();
  148.  
  149.         while(1)
  150.         {
  151.             if(tree.path[cur] == -1)
  152.                 break;
  153.  
  154.             ll dd = l-dist(u,tree.path[cur]);
  155.             ll add = upper_bound(ans[tree.path[cur]].begin(),ans[tree.path[cur]].end(),dd)-ans[tree.path[cur]].begin();
  156.             ll sub = upper_bound(cnt[u].begin(),cnt[u].end(),dd)-cnt[u].begin();
  157.  
  158.             //cout << ">>> " << add << " - " << sub << endl;
  159.  
  160.             ret += add-sub;
  161.             cur = tree.path[cur];
  162.         }
  163.         return ret;
  164.     }
  165. } ds;
  166.  
  167. int main()
  168. {
  169. #ifdef Aaman007
  170.     freopen("input.txt","r",stdin);
  171.     // freopen("output.txt","w",stdout);
  172. #endif // Aaman007
  173.  
  174.     FastRead
  175.  
  176.     ll u,v,q;
  177.     ll l,w;
  178.  
  179.     cin >> n >> q;
  180.  
  181.     for(ll i=0;i<n-1;i++)
  182.     {
  183.         cin >> u >> v >> w;
  184.         adj[u].push_back(v);
  185.         adj[v].push_back(u);
  186.         cost[{u,v}] = cost[{v,u}] = w;
  187.     }
  188.     DFS(1,1,0);
  189.     initLCA();
  190.  
  191.     tree.decompose(1,-1);
  192.  
  193.     for(ll i=1;i<=n;i++)
  194.     {
  195.         sort(ans[i].begin(),ans[i].end());
  196.         sort(cnt[i].begin(),cnt[i].end());
  197.     }
  198.  
  199.     while(q--)
  200.     {
  201.         cin >> u >> l;
  202.  
  203.         cout << ds.query(u,l) << endl;
  204.     }
  205. }
  206.  
Runtime error #stdin #stdout 0.01s 37220KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/yIUf9t
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!