Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.text.*;
- public class Main{
- //SOLUTION BEGIN
- //Into the Hardware Mode
- void pre() throws Exception{}
- void solve(int TC)throws Exception{
- n = ni(); e = ni();
- int[] from = new int[n-1], to = new int[n-1];
- int[] set = new int[n];
- for(int i = 0; i< n; i++)set[i] = i;
- for(int i = 0; i< n-1; i++){
- from[i] = ni()-1;to[i] = ni()-1;
- hold(0 <= Math.min(from[i], to[i]) && Math.max(from[i], to[i]) < n && from[i] != to[i]);
- set[find(set, from[i])] = find(set, to[i]);
- }
- g = makeU(n, from, to);
- xyz = new int[n][3];
- for(int i = 0; i< n; i++){
- xyz[i] = new int[]{ni(), ni(), ni()};
- // xyz[i] = new int[]{0, 0, 0};
- hold(0 <= Math.min(xyz[i][0], xyz[i][1]) && xyz[i][0]+xyz[i][1] <= e);
- hold(Math.abs(xyz[i][2]) <= 1e6);
- }
- t = new SegTree(n);
- ans = new long[n];
- time = -1;
- d = new int[n];sub = new int[n];ti = new int[n][2];eu = new int[n];
- d[0] = 1;
- fill(0, -1);
- dfs(0, -1, true);
- for(int i = 0; i< n; i++)if(ans[i] == IINF)ans[i] = -1;
- for(int i = 0; i< n; i++)p(ans[i]+" ");pn("");
- }
- int n, e;
- int[][] g, ti;
- int[] d, eu, sub;
- SegTree t;
- int[][] xyz;
- long[] ans;
- void dfs(int u, int p, boolean keep) throws Exception{
- int hc = -1;
- for(int v:g[u])
- if(v != p)
- if(hc == -1 || sub[v] > sub[hc])hc = v;
- for(int v:g[u])
- if(v != p && v != hc)
- dfs(v, u, false);
- if(hc != -1)dfs(hc, u, true);
- for(int v:g[u])
- if(v != hc && v != p)
- for(int i = ti[v][0]; i<= ti[v][1]; i++)
- t.add(d[eu[i]], 1);
- ans[u] = IINF;
- for(int i = 0; i<= e; i++){
- long UP = e-i;
- if(i < xyz[u][1])continue;
- if(e-i < xyz[u][0])continue;
- if(UP >= d[u])continue;
- if(i >= sub[u])continue;
- long L1 = d[u]*UP-(sum(d[u]-1)-sum(d[u]-UP-1)), R1 = d[u]*UP-sum(UP);
- long L2 = t.small(i), R2 = t.large(i);
- if(L2 == -1 || R2 == -1)continue;
- L2 -= d[u]*(long)i; R2 -= d[u]*(long)i;
- L1 += xyz[u][2];R1 += xyz[u][2];
- hold(L1 <= R1);
- hold(L2 <= R2);
- if(Math.max(L1, L2) <= Math.min(R1, R2))ans[u] = 0;
- else if(R1 < L2)ans[u] = Math.min(ans[u], L2-R1);
- else if(R2 < L1)ans[u] = Math.min(ans[u], L1-R2);
- else hold(false);
- }
- t.add(d[eu[ti[u][0]]], 1);
- if(!keep)
- for(int i = ti[u][0]; i <= ti[u][1]; i++)
- t.add(d[eu[i]], -1);
- }
- int time = -1;
- void fill(int u, int p){
- eu[++time] = u;
- ti[u][0] = time;
- sub[u]++;
- for(int v:g[u]){
- if(v != p){
- d[v] = d[u]+1;
- fill(v, u);
- sub[u] += sub[v];
- }
- }
- ti[u][1] = time;
- }
- long sum(long x){
- return (x*x+x)/2;
- }
- class SegTree{
- private int m = 1;
- private int[] count;
- private long[] sum;
- public SegTree(int mx){
- while(m <= mx)m<<=1;
- count = new int[m<<1];
- sum = new long[m<<1];
- }
- public void add(int p, int add){
- sum[p+m] += p*add;
- p += m;
- count[p] += add;
- for(p >>= 1; p > 0; p>>=1){
- sum[p] = sum[p<<1]+sum[p<<1|1];
- count[p] = count[p<<1]+count[p<<1|1];
- }
- }
- public long small(int k){
- if(count[1] < k)return -1;
- return small(k, 0, m-1, 1);
- }
- private long small(int k, int ll, int rr, int i){
- if(ll == rr){
- return k*(long)ll;
- }
- int mid = (ll+rr)/2;
- if(count[i<<1] <= k)return sum[i<<1]+small(k-count[i<<1], mid+1, rr, i<<1|1);
- return small(k, ll, mid, i<<1);
- }
- public long large(int k){
- if(count[1] < k)return -1;//sum[1];
- return large(k, 0, m-1, 1);
- }
- private long large(int k, int ll, int rr, int i){
- if(ll == rr)return k*(long)ll;
- int mid = (ll+rr)/2;
- if(count[i<<1|1] <= k)return sum[i<<1|1]+large(k-count[i<<1|1], ll, mid, i<<1);
- return large(k, mid+1, rr, i<<1|1);
- }
- public void print(){
- for(int i = m; i< m+m; i++)pn(i-m+" "+count[i]+" "+sum[i]);
- }
- }
- int[][] makeU(int n, int[]from, int[] to){
- int[][] g = new int[n][];int[] cnt = new int[n];
- for(int i:from)cnt[i]++;
- for(int i:to)cnt[i]++;
- for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
- for(int i = 0; i< from.length; i++){
- g[from[i]][--cnt[from[i]]] = to[i];
- g[to[i]][--cnt[to[i]]] = from[i];
- }
- return g;
- }
- //SOLUTION END
- void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
- void exit(boolean b){if(!b)System.exit(0);}
- long IINF = (long)1e18, mod = (long)1e9+7;
- final int INF = (int)1e9, MX = (int)2e6+5;
- DecimalFormat df = new DecimalFormat("0.0000000");
- double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
- static boolean multipleTC = true, memory = false, fileIO = false;
- FastReader in;PrintWriter out;
- void run() throws Exception{
- if(fileIO){
- in = new FastReader("C:/users/user/desktop/inp.in");
- out = new PrintWriter("C:/users/user/desktop/out.out");
- }else {
- in = new FastReader();
- out = new PrintWriter(System.out);
- }
- //Solution Credits: Taranpreet Singh
- int T = (multipleTC)?ni():1;
- pre();
- for(int t = 1; t<= T; t++)solve(t);
- out.flush();
- out.close();
- }
- public static void main(String[] args) throws Exception{
- if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
- else new Main().run();
- }
- int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
- int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
- long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
- int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
- int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
- void p(Object o){out.print(o);}
- void pn(Object o){out.println(o);}
- void pni(Object o){out.println(o);out.flush();}
- String n()throws Exception{return in.next();}
- String nln()throws Exception{return in.nextLine();}
- int ni()throws Exception{return Integer.parseInt(in.next());}
- long nl()throws Exception{return Long.parseLong(in.next());}
- double nd()throws Exception{return Double.parseDouble(in.next());}
- class FastReader{
- BufferedReader br;
- StringTokenizer st;
- public FastReader(){
- br = new BufferedReader(new InputStreamReader(System.in));
- }
- public FastReader(String s) throws Exception{
- br = new BufferedReader(new FileReader(s));
- }
- String next() throws Exception{
- while (st == null || !st.hasMoreElements()){
- try{
- st = new StringTokenizer(br.readLine());
- }catch (IOException e){
- throw new Exception(e.toString());
- }
- }
- return st.nextToken();
- }
- String nextLine() throws Exception{
- String str = "";
- try{
- str = br.readLine();
- }catch (IOException e){
- throw new Exception(e.toString());
- }
- return str;
- }
- }
- }
Add Comment
Please, Sign In to add comment