#60284 (Java) No.235 めぐるはめぐる (5)

• 問題: No.235 めぐるはめぐる (5)
• ユーザー: ぴろず
• 提出日時: 2015-11-27 17:06:56
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 2,865 ms / 10,000 ms
• コード長: 10,978 bytes
• コンパイル時間: 2,875 ms
• コンパイル使用メモリ: 91,392 KB
• 実行使用メモリ: 178,340 KB
• 最終ジャッジ日時: 2024-09-13 23:04:06
• 合計ジャッジ時間: 14,547 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
other	AC * 3

ソースコード

package meguru;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main implements Runnable{

	public static void main(String[] args) {
		new Thread(null, new Main(), "", 1024L*1024*64).start();
	}

	@Override
	public void run() {
		IO io = new IO();
		int n = io.nextInt();
		long[] s = io.nextLongArray(n);
		long[] c = io.nextLongArray(n);
		Graph g = new Graph(n);
		for(int i=0;i<n-1;i++) {
			g.addBidirectionalEdge(io.nextInt() - 1, io.nextInt() - 1);
		}
		HLDecomposition hl = g.rootedTree(0).hlDecomposition();
		int m = hl.pathnum;
		Meguru[] st = new Meguru[m];
		for(int i=0;i<m;i++) {
			st[i] = new Meguru(hl.pathSize[i]);
		}
		for(int i=0;i<n;i++) {
			st[hl.pathId[i]].setInitialValue(hl.pathIndex[i], s[i], c[i]);
		}
		for(int i=0;i<m;i++) {
			st[i].init();
		}
//		for(int i=0;i<m;i++) {
//			System.out.println(st[i]);
//		}
		int q = io.nextInt();
		for(int i=0;i<q;i++) {
			if (io.nextInt() == 0) {
				int x = io.nextInt() - 1;
				int y = io.nextInt() - 1;
				int z = io.nextInt();
				for(Query qu:hl.query(x, y)) {
					st[qu.pathId].add(qu.first, qu.last + 1, z);
				}
			}else{
				int x = io.nextInt() - 1;
				int y = io.nextInt() - 1;
				long sum = 0;
				for(Query qu:hl.query(x, y)) {
					sum += st[qu.pathId].sum(qu.first, qu.last + 1);
					if (sum >= Meguru.MOD) {
						sum -= Meguru.MOD;
					}
				}
				io.println(sum);
			}
		}
		io.flush();
	}

}
//be careful for stack overflow
class Graph {
	int n;
	ArrayList<Integer>[] edge;
	@SuppressWarnings("unchecked")
	public Graph(int n) {
		this.n = n;
		edge = new ArrayList[n];
		for(int i=0;i<n;i++) {
			edge[i] = new ArrayList<>();
		}
	}
	public void addBidirectionalEdge(int u,int v) {
		edge[u].add(v);
		edge[v].add(u);
	}
	public RootedTree rootedTree(int root) {
		return new RootedTree(this,root);
	}
}
class RootedTree {
	int n;
	int root;
	ArrayList<Integer>[] child;
	int[] parent;
	int[] in,out;
	int[] subTreeSize;
	@SuppressWarnings("unchecked")
	public RootedTree(Graph g,int root) {
		this.n = g.n;
		this.root = root;
		child = new ArrayList[n];
		for(int i=0;i<n;i++) {
			child[i] = new ArrayList<>();
		}
		parent = new int[n];
		in = new int[n];
		out = new int[n];
		subTreeSize = new int[n];
		k = 0;
		dfs(root,-1,g);
	}
	int k;
	private void dfs(int v,int p,Graph g) {
		in[v] = k++;
		parent[v] = p;
		subTreeSize[v] = 1;
		for(int u:g.edge[v]) {
			if (u == p) {
				continue;
			}
			child[v].add(u);
			dfs(u,v,g);
			subTreeSize[v] += subTreeSize[u];
		}
		out[v] = k++;
	}
	public boolean isAncestor(int parent,int child) {
		return in[parent] <= in[child] && out[child] <= out[parent];
	}
	public HLDecomposition hlDecomposition() {
		return new HLDecomposition(this);
	}
}
class HLDecomposition {
	RootedTree r;
	int[] pathId;
	int[] pathIndex;
	int[] pathRoot;
	int pathnum;
	int[] pathSize;
	public HLDecomposition(RootedTree r) {
		this.r = r;
		int n = r.n;
		pathId = new int[n];
		pathIndex = new int[n];
		pathRoot = new int[n];
		pathSize = new int[n];
		pathnum = 1;
		dfs(r.root,0,0,r.root);
//		System.out.println(Arrays.toString(pathId));
//		System.out.println(Arrays.toString(pathIndex));
//		System.out.println(Arrays.toString(pathRoot));
//		System.out.println(pathnum);
//		System.out.println(Arrays.toString(pathSize));
	}
	private void dfs(int v,int pid,int pindex,int proot) {
		pathId[v] = pid;
		pathIndex[v] = pindex;
		pathRoot[v] = proot;
		if (r.child[v].size() == 0) {
			pathSize[pid] = pindex + 1;
			return;
		}
		int maxsize = -1;
		int maxu = -1;
		for(int u:r.child[v]) {
			if (r.subTreeSize[u] > maxsize) {
				maxsize = r.subTreeSize[u];
				maxu = u;
			}
		}
		for(int u:r.child[v]) {
			if (u == maxu) {
				dfs(u,pid,pindex+1,proot);
			}else{
				dfs(u,pathnum++,0,u);
			}
		}
	}
	public ArrayList<Query> queryDirectionSensitive(int first,int last) {
		ArrayList<Query> head = new ArrayList<>();
		ArrayList<Query> tail = new ArrayList<>();
		while(!r.isAncestor(pathRoot[first], last)) {
			head.add(new Query(pathId[first], pathIndex[first], 0));
			first = r.parent[pathRoot[first]];
		}
		while(!r.isAncestor(pathRoot[last], first)) {
			tail.add(new Query(pathId[last], 0, pathIndex[last]));
			last = r.parent[pathRoot[last]];
		}
		head.add(new Query(pathId[first],pathIndex[first],pathIndex[last]));
		for(int i=tail.size()-1;i>=0;i--) {
			head.add(tail.get(i));
		}
		return head;
	}
	public ArrayList<Query> query(int u,int v) {
		ArrayList<Query> ans = queryDirectionSensitive(u,v);
		for(Query p:ans) {
			if (p.first > p.last) {
				int temp = p.first;
				p.first = p.last;
				p.last = temp;
			}
		}
//		System.out.println(ans);
		return ans;
	}
	public int lca(int u,int v) {
		while(!r.isAncestor(pathRoot[u], v)) {
			u = r.parent[pathRoot[u]];
		}
		while(!r.isAncestor(pathRoot[v], u)) {
			v = r.parent[pathRoot[v]];
		}
		return r.isAncestor(u, v) ? u : v;
	}
}
class Query {
	int pathId;
	int first,last;
	public Query(int pathId,int first,int last) {
		this.pathId = pathId;
		this.first = first;
		this.last = last;
	}
	public String toString() {
		return pathId + ":[" + first + "," + last + "]";
	}
}
class Meguru {
	public static final long MOD = 1000000007;
	private int size,n;
	long[] sum;
	long[] weight;
	private boolean[] lazy;
	private int[] lazyValue;
	public Meguru(int size) {
		this.size = size;
		n = 1;
		while(n<this.size) {
			n*=2;
		}
		sum = new long[n*2-1];
		lazy = new boolean[n*2-1];
		lazyValue = new int[n*2-1];
		weight = new long[n*2-1];
	}

	public void setInitialValue(int i,long v,long w) {
		sum[n-1+i] = v;
		weight[n-1+i] = w;
	}

	public void init() {
		for(int k=n-2;k>=0;k--) {
			sum[k] = sum[k*2+1] + sum[k*2+2];
			if (sum[k] >= MOD) {
				sum[k] -= MOD;
			}
			weight[k] = weight[k*2+1] + weight[k*2+2];
			if (weight[k] >= MOD) {
				weight[k] -= MOD;
			}
		}
	}

	private void propagate(int k) {
		if (k < n - 1 && lazy[k]) {
			for(int i=k*2+1;i<=k*2+2;i++) {
				sum[i] = (sum[i] + weight[i] * lazyValue[k]) % MOD;
				if (lazy[i]) {
					lazyValue[i] += lazyValue[k];
					if (lazyValue[i] >= MOD) {
						lazyValue[i] -= MOD;
					}
				}else{
					lazyValue[i] = lazyValue[k];
					lazy[i] = true;
				}
			}

		}
		lazy[k] = false;
	}

	public void add(int begin,int end,int x) {
		add(begin,end,x,0,0,n);
	}

	public void add(int begin,int end,int x,int k,int l,int r) {
		propagate(k);

		if (r <= begin || end <= l) {
			return;
		}
		if (begin <= l && r <= end) {
			sum[k] = (sum[k] + x * weight[k]) % MOD;
			lazy[k] = true;
			lazyValue[k] = x;
			propagate(k);
			return;
		}

		add(begin,end,x,k*2+1,l,(l+r)>>>1);
		add(begin,end,x,k*2+2,(l+r)>>>1,r);
		sum[k] = sum[k*2+1] + sum[k*2+2];
		if (sum[k] >= MOD) {
			sum[k] -= MOD;
		}
	}

	public long sum(int begin,int end) {
		return sum(begin,end,0,0,n);
	}

	private long sum(int begin,int end,int k,int l,int r) {
		propagate(k);

		if (r <= begin || end <= l) {
			return 0;
		}
		if (begin <= l && r <= end) {
			return sum[k];
		}

		long ret = sum(begin,end,k*2+1,l,(l+r)/2) + sum(begin,end,k*2+2,(l+r)/2,r);
		if (ret >= MOD) {
			ret -= MOD;
		}
		sum[k] = sum[k*2+1] + sum[k*2+2];
		if (sum[k] >= MOD) {
			sum[k] -= MOD;
		}
		return ret;
	}

	//debug
	public String toString() {
		ArrayList<Long> data = new ArrayList<>();
		for(int i=0;i<size;i++) {
			data.add(sum(i, i+1));
		}
		return data.toString();
	}
}


class IO extends PrintWriter {
	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	public IO() { this(System.in);}
	public IO(InputStream source) { super(System.out); this.in = source;}
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		}else{
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	private static boolean isNewLine(int c) { return c == '\n' || c == '\r';}
	public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; return hasNextByte();}
	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public char[] nextCharArray(int len) {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		char[] s = new char[len];
		int i = 0;
		int b = readByte();
		while(isPrintableChar(b)) {
			if (i == len) {
				throw new InputMismatchException();
			}
			s[i++] = (char) b;
			b = readByte();
		}
		return s;
	}
	public String nextLine() {
		if (!hasNextLine()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(!isNewLine(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}
	public char nextChar() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		return (char) readByte();
	}
	public double nextDouble() { return Double.parseDouble(next());}
	public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;}
	public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;}
	public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;}
	public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();}
	public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;}
	public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;}
	public void close() { super.close(); try {in.close();} catch (IOException e) {}}
}