fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty