Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class P7 {
- static ArrayList<Integer> graph[]; static int N, cent[][], dep[], sz[], par[];
- static long dist[][], val[];
- static boolean vis[];
- static long MOD = 1000000007;
- public static void main(String[] args) throws IOException {
- N = readInt(); int Q = readInt(); graph = new ArrayList[N+1];
- for(int i = 1; i<=N; i++) graph[i] = new ArrayList<Integer>();
- val = new long[N+1]; for(int i = 1; i<=N; i++) val[i] = readInt();
- for(int i = 1; i<N; i++) {int a = readInt(), b = readInt(); graph[a].add(b); graph[b].add(a);}
- dist = new long[N+1][20]; for(int i = 1; i<=N; i++) for(int d = 1; d<=19; d++) dist[i][d] = 1;
- 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];
- getCentroid(1, 1);
- long centv[] = new long[N+1];
- long centcld[] = new long[N+1];
- long startv[] = new long[N+1];
- // for(int i = 1; i<=N; i++) for(int d = 1; d<=19; d++) startv[i][d] = centv[i][d] = 0;
- long num[] = new long[N+1];
- for(int q = 0; q<Q; q++) {
- if(readInt() == 1) {
- int n = readInt(); long v = readLong();
- num[cent[n][dep[n]]]++;
- centv[cent[n][dep[n]]] = (centv[cent[n][dep[n]]]+(v*val[cent[n][dep[n]]])%MOD)%MOD;
- startv[n] = (startv[n]+v)%MOD;
- // println(cent[n][dep[n]]);
- for(int d = dep[n]-1; d>0; d--) {
- int c = cent[n][d];
- num[c]++;
- centcld[cent[n][d+1]] = (centcld[cent[n][d+1]]+(((v*dist[n][d])%MOD*val[c])%MOD*val[n])%MOD)%MOD;
- centv[c] = (centv[c]+(((v*dist[n][d])%MOD*val[c])%MOD*val[n])%MOD)%MOD;
- startv[c] = (startv[c]+((v*dist[n][d])%MOD*val[n])%MOD)%MOD;
- }
- }
- else {
- int n = readInt();
- long v = 0;
- long lastn = 0;
- v = startv[n];
- lastn = num[n];
- // println(n + " " + dep[n] + " " + lastn + " " + v);
- for(int d = dep[n]-1; d>0; d--) {
- int c = cent[n][d];
- // println(c);
- v = (v +
- ((dist[n][d])%MOD)*((centv[c]-centcld[cent[n][d+1]]+MOD)%MOD))%MOD;
- lastn = num[c];
- // println(centv[cent[n][d]] + " " + num[cent[n][d]]);
- }
- println(v);
- }
- }
- exit();
- }
- public static void getCentroid(int n, int d) {
- par[n] = 0; dfs1(n); int size = sz[n];
- while(true) {
- int hvy = 0; for(int e : graph[n]) if(!vis[e] && par[n] != e) hvy = sz[hvy] < sz[e] ? e : hvy;
- if(sz[hvy]*2 > size) n = hvy; else break;
- }
- par[n] = 0; dep[n] = d; cent[n][d] = n; dist[n][d] = 1; dfs2(n, d); vis[n] = true;
- for(int e : graph[n]) if(!vis[e]) getCentroid(e, d + 1);
- }
- public static void dfs1(int n) {
- sz[n] = 1; for(int e : graph[n]) if(!vis[e] && e != par[n]){
- par[e] = n; dfs1(e); sz[n] += sz[e];
- }
- }
- public static void dfs2(int n, int d) {
- if(par[n] == cent[n][d]) dist[n][d] = 1;
- for(int e : graph[n]) if(!vis[e] && e != par[n]) {
- par[e] = n; dist[e][d] = (dist[n][d] * val[n])%MOD; cent[e][d] = cent[n][d]; dfs2(e, d);
- }
- }
- final private static int BUFFER_SIZE = 1 << 16;
- private static DataInputStream din = new DataInputStream(System.in);
- private static byte[] buffer = new byte[BUFFER_SIZE];
- private static int bufferPointer = 0, bytesRead = 0;
- static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- public static String readLine() throws IOException {
- byte[] buf = new byte[64]; // line length
- int cnt = 0, c;
- while ((c = Read()) != -1) {
- if (c == '\n')
- break;
- buf[cnt++] = (byte) c;
- }
- return new String(buf, 0, cnt);
- }
- public static String read() throws IOException {
- byte[] ret = new byte[1024];
- int idx = 0;
- byte c = Read();
- while (c <= ' ') {
- c = Read();
- }
- do {
- ret[idx++] = c;
- c = Read();
- } while (c != -1 && c != ' ' && c != '\n' && c != '\r');
- return new String(ret, 0, idx);
- }
- public static int readInt() throws IOException {
- int ret = 0;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public static long readLong() throws IOException {
- long ret = 0;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public static double readDouble() throws IOException {
- double ret = 0, div = 1;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (c == '.') {
- while ((c = Read()) >= '0' && c <= '9') {
- ret += (c - '0') / (div *= 10);
- }
- }
- if (neg)
- return -ret;
- return ret;
- }
- private static void fillBuffer() throws IOException {
- bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
- if (bytesRead == -1)
- buffer[0] = -1;
- }
- private static byte Read() throws IOException {
- if (bufferPointer == bytesRead)
- fillBuffer();
- return buffer[bufferPointer++];
- }
- static void print(Object o) {
- pr.print(o);
- }
- static void println(Object o) {
- pr.println(o);
- }
- static void flush() {
- pr.flush();
- }
- static void println() {
- pr.println();
- }
- static void exit() throws IOException {
- din.close();
- pr.close();
- System.exit(0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement