Advertisement
ec1117

Untitled

Jul 10th, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.39 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.io.BufferedReader;
  4. import java.awt.Point;
  5.  
  6. public class disrupt{
  7. public static final String TASKNAME = "disrupt";
  8. public static long mod= 1000000007;
  9. public static Debug db;
  10.  
  11. public static void main(String[] args) throws IOException {
  12. // InputReader in = new InputReader(System.in);
  13. // PrintWriter out = new PrintWriter(System.out);
  14. InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
  15. PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
  16. Autocompletion solver = new Autocompletion();
  17. db=new Debug(System.getSecurityManager()==null);
  18. solver.solve(1, in, out);
  19. out.close();
  20. }
  21. static class Autocompletion {
  22.  
  23. public void solve(int testNumber, InputReader in, PrintWriter out) {
  24. int n=in.nextInt();
  25. int m=in.nextInt();
  26. ArrayList<Integer> adj[]=new ArrayList[n];
  27. for(int i=0;i<n;i++) {
  28. adj[i]=new ArrayList<>();
  29. }
  30. Pair query[]=new Pair[n-1];
  31. for(int i=0;i<n-1;i++) {
  32. int p=in.nextInt()-1;
  33. int q=in.nextInt()-1;
  34. query[i]=new Pair(p,q);
  35. adj[p].add(q);
  36. adj[q].add(p);
  37. }
  38. int depth[]=new int[n];
  39. int par[]=new int[n];
  40. ArrayDeque<Integer> dq=new ArrayDeque<Integer>();
  41. dq.add(0);
  42. while(!dq.isEmpty()) {
  43. int x=dq.remove();
  44. for(Integer a:adj[x]) {
  45. if(a!=par[x]) {
  46. par[a]=x;
  47. dq.add(a);
  48. depth[a]=depth[x]+1;
  49. }
  50. }
  51. }
  52. int ans[]=new int[n];
  53. Arrays.fill(ans, Integer.MAX_VALUE);
  54. for(int i=0;i<m;i++) {
  55. int p=in.nextInt()-1;
  56. int q=in.nextInt()-1;
  57. int r=in.nextInt();
  58. if(depth[p]>depth[q]) {
  59. while(depth[p]!=depth[q]) {
  60. ans[p]=Math.min(ans[p], r);
  61. p=par[p];
  62. }
  63. }
  64. if(depth[q]>depth[p]) {
  65. while(depth[p]!=depth[q]) {
  66. ans[q]=Math.min(ans[q], r);
  67. q=par[q];
  68. }
  69. }
  70. while(p!=q) {
  71. ans[p]=Math.min(ans[p], r);
  72. ans[q]=Math.min(ans[q], r);
  73. p=par[p];
  74. q=par[q];
  75. }
  76. }
  77. for(int i=0;i<n-1;i++) {
  78. Pair x=query[i];
  79. if(depth[x.x]>depth[x.y]) {
  80. if(ans[x.x]==Integer.MAX_VALUE) {
  81. out.println(-1);
  82. }
  83. else {
  84. out.println(ans[x.x]);
  85. }
  86. }
  87. else {
  88. if(ans[x.y]==Integer.MAX_VALUE) {
  89. out.println(-1);
  90. }
  91. else {
  92. out.println(ans[x.y]);
  93. }
  94. }
  95. }
  96. }
  97.  
  98. }
  99. static class Pair implements Comparable<Pair>{
  100. int x;
  101. int y;
  102. Pair(int a, int b){
  103. x=a;
  104. y=b;
  105. }
  106. @Override
  107. public int compareTo(Pair arg0) {
  108. if(arg0.x!=x)return x-arg0.x;
  109. return y-arg0.y;
  110. }
  111. }
  112. static class Triple implements Comparable<Triple>{
  113. int x;
  114. int y;
  115. int z;
  116. Triple(int a, int b, int c){
  117. x=a;
  118. y=b;
  119. z=c;
  120. }
  121. @Override
  122. public int compareTo(Triple arg0) {
  123. if(arg0.x!=x)return x-arg0.x;
  124. return y-arg0.y;
  125. }
  126. }
  127. static void bounds() {
  128. int arr[]=new int[9];
  129. System.out.println(arr[9]);
  130. }
  131. static class InputReader {
  132. public BufferedReader reader;
  133. public StringTokenizer tokenizer;
  134.  
  135. public InputReader(InputStream stream) {
  136. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  137. tokenizer = null;
  138. }
  139.  
  140. public String next() {
  141. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  142. try {
  143. tokenizer = new StringTokenizer(reader.readLine());
  144. } catch (IOException e) {
  145. throw new RuntimeException(e);
  146. }
  147. }
  148. return tokenizer.nextToken();
  149. }
  150.  
  151. public int nextInt() {
  152. return Integer.parseInt(next());
  153. }
  154. public long nextLong() {
  155. return Long.parseLong(next());
  156. }
  157. public int[] nextIntArr(int n) {
  158. int arr[]=new int[n];
  159. for(int i=0;i<n;i++) {
  160. arr[i]=this.nextInt();
  161. }
  162. return arr;
  163. }
  164. }
  165. public static class Debug {
  166. private boolean allowDebug;
  167.  
  168. public Debug(boolean allowDebug) {
  169. this.allowDebug = allowDebug;
  170. }
  171.  
  172. private void outputName(String name) {
  173. System.out.print(name + " = ");
  174. }
  175.  
  176. public void debug(String name, int x) {
  177. if (!allowDebug) {
  178. return;
  179. }
  180.  
  181. outputName(name);
  182. System.out.println("" + x);
  183. }
  184.  
  185. public void debug(String name, long x) {
  186. if (!allowDebug) {
  187. return;
  188. }
  189. outputName(name);
  190. System.out.println("" + x);
  191. }
  192.  
  193. public void debug(String name, double x) {
  194. if (!allowDebug) {
  195. return;
  196. }
  197. outputName(name);
  198. System.out.println("" + x);
  199. }
  200.  
  201. public void debug(String name, int[] x) {
  202. if (!allowDebug) {
  203. return;
  204. }
  205. outputName(name);
  206. System.out.println(Arrays.toString(x));
  207. }
  208.  
  209. public void debug(String name, long[] x) {
  210. if (!allowDebug) {
  211. return;
  212. }
  213. outputName(name);
  214. System.out.println(Arrays.toString(x));
  215. }
  216.  
  217. public void debug(String name, double[] x) {
  218. if (!allowDebug) {
  219. return;
  220. }
  221. outputName(name);
  222. System.out.println(Arrays.toString(x));
  223. }
  224.  
  225. public void debug(String name, Pair[] x) {
  226. if (!allowDebug) {
  227. return;
  228. }
  229. outputName(name);
  230. StringBuilder sb = new StringBuilder("[");
  231. int cnt=0;
  232. for(Pair y:x) {
  233. sb.append("("+y.x+","+y.y+')');
  234. if (cnt != x.length-1)sb.append(", ");
  235. cnt++;
  236. }
  237. System.out.println(sb.append("]").toString());
  238. }
  239.  
  240. public void debug(String name, Object x) {
  241. if (!allowDebug) {
  242. return;
  243. }
  244. outputName(name);
  245. System.out.println("" + x);
  246. }
  247.  
  248. public void debug(String name, Object... x) {
  249. if (!allowDebug) {
  250. return;
  251. }
  252. outputName(name);
  253. System.out.println(Arrays.deepToString(x));
  254. }
  255. }
  256. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement