Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.44 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class P7 {
  5.  
  6. static ArrayList<Integer> graph[]; static int N, cent[][], dep[], sz[], par[];
  7. static long dist[][], val[];
  8. static boolean vis[];
  9. static long MOD = 1000000007;
  10.  
  11. public static void main(String[] args) throws IOException {
  12. N = readInt(); int Q = readInt(); graph = new ArrayList[N+1];
  13. for(int i = 1; i<=N; i++) graph[i] = new ArrayList<Integer>();
  14. val = new long[N+1]; for(int i = 1; i<=N; i++) val[i] = readInt();
  15. for(int i = 1; i<N; i++) {int a = readInt(), b = readInt(); graph[a].add(b); graph[b].add(a);}
  16. dist = new long[N+1][20]; for(int i = 1; i<=N; i++) for(int d = 1; d<=19; d++) dist[i][d] = 1;
  17. cent = new int[N+1][20]; dep = new int[N+1]; sz = new int[N+1]; par = new int[N+1]; vis = new boolean[N+1];
  18. getCentroid(1, 1);
  19. long centv[] = new long[N+1];
  20. long centcld[] = new long[N+1];
  21. long startv[] = new long[N+1];
  22. // for(int i = 1; i<=N; i++) for(int d = 1; d<=19; d++) startv[i][d] = centv[i][d] = 0;
  23. long num[] = new long[N+1];
  24. for(int q = 0; q<Q; q++) {
  25. if(readInt() == 1) {
  26. int n = readInt(); long v = readLong();
  27. num[cent[n][dep[n]]]++;
  28. centv[cent[n][dep[n]]] = (centv[cent[n][dep[n]]]+(v*val[cent[n][dep[n]]])%MOD)%MOD;
  29. startv[n] = (startv[n]+v)%MOD;
  30. // println(cent[n][dep[n]]);
  31. for(int d = dep[n]-1; d>0; d--) {
  32. int c = cent[n][d];
  33. num[c]++;
  34. centcld[cent[n][d+1]] = (centcld[cent[n][d+1]]+(((v*dist[n][d])%MOD*val[c])%MOD*val[n])%MOD)%MOD;
  35. centv[c] = (centv[c]+(((v*dist[n][d])%MOD*val[c])%MOD*val[n])%MOD)%MOD;
  36. startv[c] = (startv[c]+((v*dist[n][d])%MOD*val[n])%MOD)%MOD;
  37. }
  38. }
  39. else {
  40. int n = readInt();
  41. long v = 0;
  42. long lastn = 0;
  43. v = startv[n];
  44. lastn = num[n];
  45. // println(n + " " + dep[n] + " " + lastn + " " + v);
  46. for(int d = dep[n]-1; d>0; d--) {
  47. int c = cent[n][d];
  48. // println(c);
  49. v = (v +
  50. ((dist[n][d])%MOD)*((centv[c]-centcld[cent[n][d+1]]+MOD)%MOD))%MOD;
  51. lastn = num[c];
  52. // println(centv[cent[n][d]] + " " + num[cent[n][d]]);
  53. }
  54. println(v);
  55. }
  56. }
  57. exit();
  58. }
  59.  
  60. public static void getCentroid(int n, int d) {
  61. par[n] = 0; dfs1(n); int size = sz[n];
  62. while(true) {
  63. int hvy = 0; for(int e : graph[n]) if(!vis[e] && par[n] != e) hvy = sz[hvy] < sz[e] ? e : hvy;
  64. if(sz[hvy]*2 > size) n = hvy; else break;
  65. }
  66. par[n] = 0; dep[n] = d; cent[n][d] = n; dist[n][d] = 1; dfs2(n, d); vis[n] = true;
  67. for(int e : graph[n]) if(!vis[e]) getCentroid(e, d + 1);
  68. }
  69.  
  70. public static void dfs1(int n) {
  71. sz[n] = 1; for(int e : graph[n]) if(!vis[e] && e != par[n]){
  72. par[e] = n; dfs1(e); sz[n] += sz[e];
  73. }
  74. }
  75.  
  76. public static void dfs2(int n, int d) {
  77. if(par[n] == cent[n][d]) dist[n][d] = 1;
  78. for(int e : graph[n]) if(!vis[e] && e != par[n]) {
  79. par[e] = n; dist[e][d] = (dist[n][d] * val[n])%MOD; cent[e][d] = cent[n][d]; dfs2(e, d);
  80. }
  81. }
  82.  
  83. final private static int BUFFER_SIZE = 1 << 16;
  84. private static DataInputStream din = new DataInputStream(System.in);
  85. private static byte[] buffer = new byte[BUFFER_SIZE];
  86. private static int bufferPointer = 0, bytesRead = 0;
  87. static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  88.  
  89. public static String readLine() throws IOException {
  90. byte[] buf = new byte[64]; // line length
  91. int cnt = 0, c;
  92. while ((c = Read()) != -1) {
  93. if (c == '\n')
  94. break;
  95. buf[cnt++] = (byte) c;
  96. }
  97. return new String(buf, 0, cnt);
  98. }
  99.  
  100. public static String read() throws IOException {
  101. byte[] ret = new byte[1024];
  102. int idx = 0;
  103. byte c = Read();
  104. while (c <= ' ') {
  105. c = Read();
  106. }
  107. do {
  108. ret[idx++] = c;
  109. c = Read();
  110. } while (c != -1 && c != ' ' && c != '\n' && c != '\r');
  111. return new String(ret, 0, idx);
  112. }
  113.  
  114. public static int readInt() throws IOException {
  115. int ret = 0;
  116. byte c = Read();
  117. while (c <= ' ')
  118. c = Read();
  119. boolean neg = (c == '-');
  120. if (neg)
  121. c = Read();
  122. do {
  123. ret = ret * 10 + c - '0';
  124. } while ((c = Read()) >= '0' && c <= '9');
  125.  
  126. if (neg)
  127. return -ret;
  128. return ret;
  129. }
  130.  
  131. public static long readLong() throws IOException {
  132. long ret = 0;
  133. byte c = Read();
  134. while (c <= ' ')
  135. c = Read();
  136. boolean neg = (c == '-');
  137. if (neg)
  138. c = Read();
  139. do {
  140. ret = ret * 10 + c - '0';
  141. } while ((c = Read()) >= '0' && c <= '9');
  142. if (neg)
  143. return -ret;
  144. return ret;
  145. }
  146.  
  147. public static double readDouble() throws IOException {
  148. double ret = 0, div = 1;
  149. byte c = Read();
  150. while (c <= ' ')
  151. c = Read();
  152. boolean neg = (c == '-');
  153. if (neg)
  154. c = Read();
  155.  
  156. do {
  157. ret = ret * 10 + c - '0';
  158. } while ((c = Read()) >= '0' && c <= '9');
  159.  
  160. if (c == '.') {
  161. while ((c = Read()) >= '0' && c <= '9') {
  162. ret += (c - '0') / (div *= 10);
  163. }
  164. }
  165.  
  166. if (neg)
  167. return -ret;
  168. return ret;
  169. }
  170.  
  171. private static void fillBuffer() throws IOException {
  172. bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  173. if (bytesRead == -1)
  174. buffer[0] = -1;
  175. }
  176.  
  177. private static byte Read() throws IOException {
  178. if (bufferPointer == bytesRead)
  179. fillBuffer();
  180. return buffer[bufferPointer++];
  181. }
  182.  
  183. static void print(Object o) {
  184. pr.print(o);
  185. }
  186.  
  187. static void println(Object o) {
  188. pr.println(o);
  189. }
  190.  
  191. static void flush() {
  192. pr.flush();
  193. }
  194.  
  195. static void println() {
  196. pr.println();
  197. }
  198.  
  199. static void exit() throws IOException {
  200. din.close();
  201. pr.close();
  202. System.exit(0);
  203. }
  204. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement