Guest User

Untitled

a guest
Oct 22nd, 2019
69
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*input
  2.  
  3. */
  4. #include<bits/stdc++.h>
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. using namespace std;
  8. using namespace __gnu_pbds;
  9.  
  10. #define int long long
  11. #define double long double
  12. #define f first
  13. #define s second
  14. #define mp make_pair
  15. #define pb push_back
  16.  
  17. #define RE(i,n) for (int i = 1; i <= n; i++)
  18. #define RED(i,n) for (int i = n; i > 0; i--)
  19. #define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
  20. #define REP(i,n) for (int i = 0; i < (int)n; i++)
  21. #define FOR(i,a,b) for (int i = a; i < b; i++)
  22. #define REPD(i,n) for (int i = n-1; i >= 0; i--)
  23. #define FORD(i,a,b) for (int i = a; i >= b; i--)
  24.  
  25. #define all(v) v.begin(),v.end()
  26. #define pii pair<int,int>
  27. #define vi vector<int>
  28. #define vvi vector<vi>
  29. #define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
  30. #define debug(x) cout << x << endl;
  31. #define debug2(x,y) cout << x << " " << y << endl;
  32. #define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
  33.  
  34. typedef tree<
  35. int,
  36. null_type,
  37. less<int>,
  38. rb_tree_tag,
  39. tree_order_statistics_node_update>
  40. ordered_set;
  41.  
  42. const int INF = 1e18+1;
  43. const int MOD = 1e9+7;
  44. const double PI = 3.14159265358979323846264338;
  45.  
  46. int raise(int a,int n,int m = MOD){
  47.   if(n == 0)return 1;
  48.   if(n == 1)return a;
  49.   int x = 1;
  50.     x *= raise(a,n/2,m);
  51.     x %= m;
  52.     x *= x;
  53.     x %= m;
  54.     if(n%2)x*= a;
  55.     x %= m;
  56.     return x;
  57. }
  58.  
  59. int floor1(int n,int k){
  60.     if(n%k == 0 || n >= 0)return n/k;
  61.     return (n/k)-1;
  62. }
  63.  
  64. int ceil1(int n,int k){
  65.     return floor1(n+k-1,k);
  66. }
  67.  
  68. // first to dfs to calculate numbers and
  69. // need persistent segtree on dfs numbers
  70. // need to write binary search
  71. const int N = 2e5+1;
  72. int n,e;
  73. vector<int> adj[N];
  74. int sub[N];
  75. int en[N];
  76. int dist[N];
  77. int inv[N];
  78. int ans[N];
  79. int x[N];
  80. int y[N];
  81. int z[N];
  82. int cur = 0;
  83.  
  84. void ini(){
  85.     cur = 0;
  86.     dist[1] = 0;
  87.     RE(i,n){
  88.       adj[i].clear();  
  89.     }
  90. }
  91.  
  92. struct node{
  93.     int cnt,sum;
  94.     node *l,*r;
  95.     node(){
  96.       cnt = 0;
  97.       sum = 0;
  98.       l = NULL;
  99.       r = NULL;
  100.     }
  101.     node(int a,int b,node* l1,node* r1){
  102.       cnt = a;
  103.       sum = b;
  104.       l = l1;
  105.       r = r1;
  106.     }
  107. };
  108.  
  109. node *roots[N];
  110.  
  111. void dfs(int u,int p){
  112.     cur++;
  113.     inv[cur] = u;
  114.     en[u] = cur;
  115.     sub[u] = 1;
  116.     for(int v:adj[u]){
  117.       if(v == p)continue;
  118.       dist[v] = dist[u]+1;
  119.       dfs(v,u);
  120.       sub[u] += sub[v];
  121.     }
  122. }
  123.  
  124.  
  125.  
  126. #define mid (le+re)/2
  127. #define child 2*node
  128. // remember to undef this XD
  129.  
  130. void build(node* cur,int le,int re){
  131.     if(le == re)return;
  132.     cur->l = new node();
  133.     cur->r = new node();
  134.     build(cur->l,le,mid);
  135.     build(cur->r,mid+1,re);
  136. }
  137.  
  138. node* inse(node* cur,int le,int re,int ind){
  139.     if(ind > re or ind < le)return cur;
  140.     if(le == re){
  141.       return new node(cur->cnt+1,cur->sum+ind,NULL,NULL);
  142.     }
  143.     node* res = new node(cur->cnt+1,cur->sum+ind,inse(cur->l,le,mid,ind),inse(cur->r,mid+1,re,ind));
  144.     return res;
  145. }
  146.  
  147. int query(node* st,node* ent,int le,int re,int left,int cursum){
  148.     if(le == re){
  149.       return cursum+left*le;
  150.     }
  151.     if(ent->r->cnt-st->r->cnt >= left)return query(st->r,ent->r,mid+1,re,left,cursum);
  152.     int addsum = ent->r->sum-st->r->sum;
  153.     int lesscnt = ent->r->cnt-st->r->cnt;
  154.     return query(st->l,ent->l,le,mid,left-lesscnt,cursum+addsum);
  155. }
  156.  
  157. int querys(node* st,node* ent,int le,int re,int left,int cursum){
  158.     if(le == re){
  159.       return cursum+left*le;
  160.     }
  161.     if(ent->l->cnt-st->l->cnt >= left)return querys(st->l,ent->l,le,mid,left,cursum);
  162.     int addsum = ent->l->sum-st->l->sum;
  163.     int lesscnt = ent->l->cnt-st->l->cnt;
  164.     return querys(st->r,ent->r,mid+1,re,left-lesscnt,cursum+addsum);
  165. }
  166.  
  167. #undef mid
  168. //haha done nice nice
  169. int resL1(int node,int place){
  170.     int res = place*(place+1);
  171.     return res/2;
  172. }
  173.  
  174. int resR1(int node,int place){
  175.     int tot = dist[node]*(dist[node]-1);
  176.     int place1 = dist[node]-1-place;
  177.     int minus = place1*(place1+1);
  178.     return (tot-minus)/2;
  179. }
  180.  
  181. int resL2(int node,int place){
  182.     return querys(roots[en[node]],roots[en[node]+sub[node]-1],1,n,place,0);
  183. }
  184.  
  185. int resR2(int node,int place){
  186.     return query(roots[en[node]],roots[en[node]+sub[node]-1],1,n,place,0);
  187. }
  188.  
  189. int val = 0;
  190.  
  191. int LRE(int node,int above){
  192.     assert(above >= x[node]);
  193.     assert(e-above >= y[node]);
  194.     assert(above <= dist[node]-1);
  195.     assert(e-above <= sub[node]-1);
  196.     int l1 = resL1(node,above);
  197.     int r1 = resR1(node,above);
  198.     int l2 = resL2(node,e-above);
  199.     int r2 = resR2(node,e-above);
  200.     l2 -= (e-above)*dist[node];
  201.     r2 -= (e-above)*dist[node];
  202.     l1 += z[node];
  203.     r1 += z[node];
  204.     if(r1 < l2){
  205.       val = l2-r1;
  206.       return 1;
  207.     }
  208.     else if(r2 < l1){
  209.       val = l1-r2;
  210.       return 2;
  211.     }
  212.     val = 0;
  213.     return 0;
  214. }
  215.  
  216. void solve(){
  217.     cin >> n >> e;
  218.     ini();
  219.     RE(i,n-1){
  220.       int a,b;cin >>a >> b;
  221.       adj[a].pb(b);
  222.       adj[b].pb(a);
  223.     }
  224.     RE(i,n){
  225.       cin >> x[i] >> y[i] >> z[i];
  226.     }
  227.     dist[1] = 1;
  228.     dfs(1,0);
  229.  
  230.     roots[0] = new node();
  231.     build(roots[0],1,n);
  232.     RE(i,n){
  233.       roots[i] = inse(roots[i-1],1,n,dist[inv[i]]);
  234.     }
  235.     RE(i,n){
  236.       int lo = x[i];
  237.       int hi = e-y[i];
  238.       hi = min(hi,dist[i]-1);
  239.       if(sub[i]-1+dist[i]-1 < e or lo > hi or lo > dist[i]-1){
  240.         ans[i] = -1;
  241.         continue;
  242.       }
  243.       lo = max(lo,e-sub[i]+1);
  244.       int intial = LRE(i,lo);
  245.       int final = LRE(i,hi);
  246.       if(intial == final){
  247.         LRE(i,lo);
  248.         ans[i] = val;
  249.         LRE(i,hi);
  250.         ans[i] = min(ans[i],val);
  251.         continue;
  252.       }
  253.       while(lo < hi){
  254.         int mid = (lo+hi)/2;
  255.         int whatcase = LRE(i,mid);
  256.         if(whatcase == intial)lo = mid+1;
  257.         else{
  258.           hi = mid;
  259.         }
  260.       }
  261.       LRE(i,lo-1);
  262.       ans[i] = val;
  263.       LRE(i,lo);
  264.       ans[i] = min(ans[i],val);
  265.     }
  266.     RE(i,n){
  267.       cout << ans[i] << " ";
  268.     }
  269.     cout << endl;
  270. }
  271.  
  272. signed main(){
  273.   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  274.   int t = 1;
  275.   cin >> t;
  276.   while(t--){
  277.     solve();
  278.   }
  279.   return 0;
  280. }
RAW Paste Data