# Untitled

a guest
Oct 22nd, 2019
27
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import java.util.*;
2. import java.io.*;
3. import java.text.*;
4. public class Main{
5.     //SOLUTION BEGIN
6.     //Into the Hardware Mode
7.     void pre() throws Exception{}
8.     void solve(int TC)throws Exception{
9.         n = ni(); e = ni();
10.         int[] from = new int[n-1], to = new int[n-1];
11.         int[] set = new int[n];
12.         for(int i = 0; i< n; i++)set[i] = i;
13.         for(int i = 0; i< n-1; i++){
14.             from[i] = ni()-1;to[i] = ni()-1;
15.             hold(0 <= Math.min(from[i], to[i]) && Math.max(from[i], to[i]) < n && from[i] != to[i]);
16.             set[find(set, from[i])] = find(set, to[i]);
17.         }
18.         g = makeU(n, from, to);
19.         xyz = new int[n][3];
20.         for(int i = 0; i< n; i++){
21.             xyz[i] = new int[]{ni(), ni(), ni()};
22. //            xyz[i] = new int[]{0, 0, 0};
23.             hold(0 <= Math.min(xyz[i][0], xyz[i][1]) && xyz[i][0]+xyz[i][1] <= e);
24.             hold(Math.abs(xyz[i][2]) <= 1e6);
25.         }
26.         t = new SegTree(n);
27.         ans = new long[n];
28.         time = -1;
29.         d = new int[n];sub = new int[n];ti = new int[n][2];eu = new int[n];
30.         d[0] = 1;
31.         fill(0, -1);
32.         dfs(0, -1, true);
33.         for(int i = 0; i< n; i++)if(ans[i] == IINF)ans[i] = -1;
34.         for(int i = 0; i< n; i++)p(ans[i]+" ");pn("");
35.     }
36.     int n, e;
37.     int[][] g, ti;
38.     int[] d, eu, sub;
39.     SegTree t;
40.     int[][] xyz;
41.     long[] ans;
42.     void dfs(int u, int p, boolean keep) throws Exception{
43.         int hc = -1;
44.         for(int v:g[u])
45.             if(v != p)
46.                 if(hc == -1 || sub[v] > sub[hc])hc = v;
47.
48.         for(int v:g[u])
49.             if(v != p && v != hc)
50.                 dfs(v, u, false);
51.         if(hc != -1)dfs(hc, u, true);
52.
53.         for(int v:g[u])
54.             if(v != hc && v != p)
55.                 for(int i = ti[v][0]; i<= ti[v][1]; i++)
57.
58.         ans[u] = IINF;
59.         for(int i = 0; i<= e; i++){
60.             long UP = e-i;
61.             if(i < xyz[u][1])continue;
62.             if(e-i < xyz[u][0])continue;
63.             if(UP >= d[u])continue;
64.             if(i >= sub[u])continue;
65.             long L1 = d[u]*UP-(sum(d[u]-1)-sum(d[u]-UP-1)), R1 = d[u]*UP-sum(UP);
66.
67.             long L2 = t.small(i), R2 = t.large(i);
68.             if(L2 == -1 || R2 == -1)continue;
69.             L2  -= d[u]*(long)i; R2 -= d[u]*(long)i;
70.             L1 += xyz[u][2];R1 += xyz[u][2];
71.
72.             hold(L1 <= R1);
73.             hold(L2 <= R2);
74.
75.             if(Math.max(L1, L2) <= Math.min(R1, R2))ans[u] = 0;
76.             else if(R1 < L2)ans[u] = Math.min(ans[u], L2-R1);
77.             else if(R2 < L1)ans[u] = Math.min(ans[u], L1-R2);
78.             else hold(false);
79.         }
80.
82.         if(!keep)
83.             for(int i = ti[u][0]; i <= ti[u][1]; i++)
85.     }
86.     int time = -1;
87.     void fill(int u, int p){
88.         eu[++time] = u;
89.         ti[u][0] = time;
90.         sub[u]++;
91.         for(int v:g[u]){
92.             if(v != p){
93.                 d[v] = d[u]+1;
94.                 fill(v, u);
95.                 sub[u] += sub[v];
96.             }
97.         }
98.         ti[u][1] = time;
99.     }
100.     long sum(long x){
101.         return (x*x+x)/2;
102.     }
103.     class SegTree{
104.         private int m = 1;
105.         private int[] count;
106.         private long[] sum;
107.         public SegTree(int mx){
108.             while(m <= mx)m<<=1;
109.             count = new int[m<<1];
110.             sum = new long[m<<1];
111.         }
114.             p += m;
116.             for(p >>= 1; p > 0; p>>=1){
117.                 sum[p] = sum[p<<1]+sum[p<<1|1];
118.                 count[p] = count[p<<1]+count[p<<1|1];
119.             }
120.         }
121.         public long small(int k){
122.             if(count[1] < k)return -1;
123.             return small(k, 0, m-1, 1);
124.         }
125.         private long small(int k, int ll, int rr, int i){
126.             if(ll == rr){
127.                 return k*(long)ll;
128.             }
129.             int mid = (ll+rr)/2;
130.             if(count[i<<1] <= k)return sum[i<<1]+small(k-count[i<<1], mid+1, rr, i<<1|1);
131.             return small(k, ll, mid, i<<1);
132.         }
133.         public long large(int k){
134.             if(count[1] < k)return -1;//sum[1];
135.             return large(k, 0, m-1, 1);
136.         }
137.         private long large(int k, int ll, int rr, int i){
138.             if(ll == rr)return k*(long)ll;
139.             int mid = (ll+rr)/2;
140.             if(count[i<<1|1] <= k)return sum[i<<1|1]+large(k-count[i<<1|1], ll, mid, i<<1);
141.             return large(k, mid+1, rr, i<<1|1);
142.         }
143.         public void print(){
144.             for(int i = m; i< m+m; i++)pn(i-m+" "+count[i]+" "+sum[i]);
145.         }
146.     }
147.     int[][] makeU(int n, int[]from, int[] to){
148.         int[][] g = new int[n][];int[] cnt = new int[n];
149.         for(int i:from)cnt[i]++;
150.         for(int i:to)cnt[i]++;
151.         for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
152.         for(int i = 0; i< from.length; i++){
153.             g[from[i]][--cnt[from[i]]] = to[i];
154.             g[to[i]][--cnt[to[i]]] = from[i];
155.         }
156.         return g;
157.     }
158.     //SOLUTION END
159.     void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
160.     void exit(boolean b){if(!b)System.exit(0);}
161.     long IINF = (long)1e18, mod = (long)1e9+7;
162.     final int INF = (int)1e9, MX = (int)2e6+5;
163.     DecimalFormat df = new DecimalFormat("0.0000000");
164.     double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
165.     static boolean multipleTC = true, memory = false, fileIO = false;
167.     void run() throws Exception{
168.         if(fileIO){
170.             out = new PrintWriter("C:/users/user/desktop/out.out");
171.         }else {
173.             out = new PrintWriter(System.out);
174.         }
175.         //Solution Credits: Taranpreet Singh
176.         int T = (multipleTC)?ni():1;
177.         pre();
178.         for(int t = 1; t<= T; t++)solve(t);
179.         out.flush();
180.         out.close();
181.     }
182.     public static void main(String[] args) throws Exception{
183.         if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
184.         else new Main().run();
185.     }
186.     int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
187.     int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
188.     long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
189.     int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
190.     int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
191.     void p(Object o){out.print(o);}
192.     void pn(Object o){out.println(o);}
193.     void pni(Object o){out.println(o);out.flush();}
194.     String n()throws Exception{return in.next();}
195.     String nln()throws Exception{return in.nextLine();}
196.     int ni()throws Exception{return Integer.parseInt(in.next());}
197.     long nl()throws Exception{return Long.parseLong(in.next());}
198.     double nd()throws Exception{return Double.parseDouble(in.next());}
199.
202.         StringTokenizer st;
205.         }
206.
207.         public FastReader(String s) throws Exception{
209.         }
210.
211.         String next() throws Exception{
212.             while (st == null || !st.hasMoreElements()){
213.                 try{
215.                 }catch (IOException  e){
216.                     throw new Exception(e.toString());
217.                 }
218.             }
219.             return st.nextToken();
220.         }
221.
222.         String nextLine() throws Exception{
223.             String str = "";
224.             try{