Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.io.BufferedReader;
- import java.awt.Point;
- public class disrupt{
- public static final String TASKNAME = "disrupt";
- public static long mod= 1000000007;
- public static Debug db;
- public static void main(String[] args) throws IOException {
- // InputReader in = new InputReader(System.in);
- // PrintWriter out = new PrintWriter(System.out);
- InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
- PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
- Autocompletion solver = new Autocompletion();
- db=new Debug(System.getSecurityManager()==null);
- solver.solve(1, in, out);
- out.close();
- }
- static class Autocompletion {
- public void solve(int testNumber, InputReader in, PrintWriter out) {
- int n=in.nextInt();
- int m=in.nextInt();
- ArrayList<Integer> adj[]=new ArrayList[n];
- for(int i=0;i<n;i++) {
- adj[i]=new ArrayList<>();
- }
- Pair query[]=new Pair[n-1];
- for(int i=0;i<n-1;i++) {
- int p=in.nextInt()-1;
- int q=in.nextInt()-1;
- query[i]=new Pair(p,q);
- adj[p].add(q);
- adj[q].add(p);
- }
- int depth[]=new int[n];
- int par[]=new int[n];
- ArrayDeque<Integer> dq=new ArrayDeque<Integer>();
- dq.add(0);
- while(!dq.isEmpty()) {
- int x=dq.remove();
- for(Integer a:adj[x]) {
- if(a!=par[x]) {
- par[a]=x;
- dq.add(a);
- depth[a]=depth[x]+1;
- }
- }
- }
- int ans[]=new int[n];
- Arrays.fill(ans, Integer.MAX_VALUE);
- for(int i=0;i<m;i++) {
- int p=in.nextInt()-1;
- int q=in.nextInt()-1;
- int r=in.nextInt();
- if(depth[p]>depth[q]) {
- while(depth[p]!=depth[q]) {
- ans[p]=Math.min(ans[p], r);
- p=par[p];
- }
- }
- if(depth[q]>depth[p]) {
- while(depth[p]!=depth[q]) {
- ans[q]=Math.min(ans[q], r);
- q=par[q];
- }
- }
- while(p!=q) {
- ans[p]=Math.min(ans[p], r);
- ans[q]=Math.min(ans[q], r);
- p=par[p];
- q=par[q];
- }
- }
- for(int i=0;i<n-1;i++) {
- Pair x=query[i];
- if(depth[x.x]>depth[x.y]) {
- if(ans[x.x]==Integer.MAX_VALUE) {
- out.println(-1);
- }
- else {
- out.println(ans[x.x]);
- }
- }
- else {
- if(ans[x.y]==Integer.MAX_VALUE) {
- out.println(-1);
- }
- else {
- out.println(ans[x.y]);
- }
- }
- }
- }
- }
- static class Pair implements Comparable<Pair>{
- int x;
- int y;
- Pair(int a, int b){
- x=a;
- y=b;
- }
- @Override
- public int compareTo(Pair arg0) {
- if(arg0.x!=x)return x-arg0.x;
- return y-arg0.y;
- }
- }
- static class Triple implements Comparable<Triple>{
- int x;
- int y;
- int z;
- Triple(int a, int b, int c){
- x=a;
- y=b;
- z=c;
- }
- @Override
- public int compareTo(Triple arg0) {
- if(arg0.x!=x)return x-arg0.x;
- return y-arg0.y;
- }
- }
- static void bounds() {
- int arr[]=new int[9];
- System.out.println(arr[9]);
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public int[] nextIntArr(int n) {
- int arr[]=new int[n];
- for(int i=0;i<n;i++) {
- arr[i]=this.nextInt();
- }
- return arr;
- }
- }
- public static class Debug {
- private boolean allowDebug;
- public Debug(boolean allowDebug) {
- this.allowDebug = allowDebug;
- }
- private void outputName(String name) {
- System.out.print(name + " = ");
- }
- public void debug(String name, int x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, long x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, double x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, int[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, long[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, double[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, Pair[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- StringBuilder sb = new StringBuilder("[");
- int cnt=0;
- for(Pair y:x) {
- sb.append("("+y.x+","+y.y+')');
- if (cnt != x.length-1)sb.append(", ");
- cnt++;
- }
- System.out.println(sb.append("]").toString());
- }
- public void debug(String name, Object x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, Object... x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.deepToString(x));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement