Guest User

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++)
  56.                     t.add(d[eu[i]], 1);
  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.        
  81.         t.add(d[eu[ti[u][0]]], 1);
  82.         if(!keep)
  83.             for(int i = ti[u][0]; i <= ti[u][1]; i++)
  84.                 t.add(d[eu[i]], -1);
  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.         }
  112.         public void add(int p, int add){
  113.             sum[p+m] += p*add;
  114.             p += m;
  115.             count[p] += add;
  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;
  166.     FastReader in;PrintWriter out;
  167.     void run() throws Exception{
  168.         if(fileIO){
  169.             in = new FastReader("C:/users/user/desktop/inp.in");
  170.             out = new PrintWriter("C:/users/user/desktop/out.out");
  171.         }else {
  172.             in = new FastReader();
  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.  
  200.     class FastReader{
  201.         BufferedReader br;
  202.         StringTokenizer st;
  203.         public FastReader(){
  204.             br = new BufferedReader(new InputStreamReader(System.in));
  205.         }
  206.  
  207.         public FastReader(String s) throws Exception{
  208.             br = new BufferedReader(new FileReader(s));
  209.         }
  210.  
  211.         String next() throws Exception{
  212.             while (st == null || !st.hasMoreElements()){
  213.                 try{
  214.                     st = new StringTokenizer(br.readLine());
  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{  
  225.                 str = br.readLine();
  226.             }catch (IOException e){
  227.                 throw new Exception(e.toString());
  228.             }  
  229.             return str;
  230.         }
  231.     }  
  232. }
RAW Paste Data