fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #include<ext/pb_ds/assoc_container.hpp>
  5. #include<ext/pb_ds/tree_policy.hpp>
  6. using namespace __gnu_pbds;
  7. template <typename T>
  8. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  9.  
  10. //0 1->codeforces
  11. #define LL "%lld"
  12. #define fi first
  13. #define se second
  14. #define pb push_back
  15. #define mp make_pair
  16. #define PN printf("\n")
  17. #define MODV 1000000007
  18. #define MAXN 100007
  19.  
  20. typedef long long ll;
  21. typedef double dbl;
  22. typedef vector<int> vi;
  23. typedef vector<ll> vll;
  24. typedef pair<int, int> pi;
  25. void addmod(int &a, ll b){a=(a+b); if(a>=MODV)a-=MODV;}
  26. void mulmod(int &a, ll b){a=(a*b)%MODV;}
  27. int gi(){int a;scanf("%d",&a);return a;}
  28. ll gll(){ll a;scanf(LL,&a);return a;}
  29.  
  30. typedef ordered_set<pair<ll,int>> opi;
  31. //ordered_set<opi> os[MAXN];
  32. ll ans[MAXN], dw[MAXN];
  33. vector<pi> vq[MAXN];
  34.  
  35. class graphwal
  36. {
  37.   public:
  38.     //1 1->bidirectional, 2->reverse edges
  39.     typedef vector<pair<int,int>> vpi;
  40.  
  41.     int n, q;
  42.     vector<vpi> ed;
  43.  
  44.     graphwal(int n):n(n),ed(n){}
  45.     void add(int a, int b, ll w){
  46.       if(ed[a].size()==0)ed[a].reserve(8);
  47.       if(ed[b].size()==0)ed[b].reserve(8);
  48.       ed[a].pb(mp(b,w));ed[b].pb(mp(a,w));
  49.     }
  50.     void load(int m){ for(int i=0;i<m;i++){int a=gi(),b=gi();int w=gi();add(a-1,b-1,w);}}
  51.     void loadq(int q){
  52.       this->q = q;
  53.       int v;int k;
  54.       for(int i=0;i<q;i++){
  55.         v=gi()-1;k=gi();
  56.         if(k>n)ans[i]=-1;
  57.         else{
  58.           if(vq[v].size()==0)vq[v].reserve(8);
  59.           vq[v].pb({k,i});
  60.         }
  61.       }
  62.     }
  63.     void merge(opi &oa, opi &ob, int ia, int ib){
  64.       if(oa.size()<ob.size()){
  65.         swap(oa,ob);
  66.         swap(dw[ia],dw[ib]);
  67.       }
  68.       ll diff=dw[ib]-dw[ia];
  69.       for(auto it=ob.begin();it!=ob.end();it++){
  70.         oa.insert({(*it).fi+diff,(*it).se});
  71.       }
  72.     }
  73.     opi dfs(int v=0, int pa=-1){
  74.       bool leaf=true;
  75.       opi o;
  76.       for(auto i:ed[v])
  77.         if(i.fi!=pa){
  78.           leaf=false;
  79.           opi t=dfs(i.fi,v);
  80.           dw[i.fi]+=i.se;
  81.           merge(o,t,v,i.fi);
  82.         }
  83.       int sz=o.size();
  84.       for(auto i:vq[v]){
  85.         if(i.fi>sz){
  86.           ans[i.se]=-1;
  87.         }else{
  88.           ans[i.se]=(*o.find_by_order(i.fi-1)).fi+dw[v];
  89.         }
  90.       }
  91.       o.insert({-dw[v],v});
  92.       return o;
  93.     }
  94.     void print(){
  95.       for(int i=0;i<q;i++){
  96.         printf("%lld\n",ans[i]);
  97.       }
  98.     }
  99. };
  100. int main() {
  101.   int n=gi();
  102.   graphwal g(n);
  103.   g.load(n-1);
  104.   g.loadq(gi());
  105.   g.dfs();
  106.   g.print();
  107.  
  108.   return 0;
  109. }
  110.  
Runtime error #stdin #stdout 0s 6200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QydU6N
language:
C++14 (gcc 8.3)
created:
8 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!