#540867 (Java21) No.1038 TreeAddQuery

提出ソース

結果

問題	No.1038 TreeAddQuery
ユーザー	uwi
提出日時	2020-08-27 13:38:17
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,576 ms / 4,000 ms
コード長	12,696 bytes
コンパイル時間	4,546 ms
コンパイル使用メモリ	89,904 KB
実行使用メモリ	122,524 KB
最終ジャッジ日時	2024-04-25 06:05:42
合計ジャッジ時間	31,641 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	52 ms 36,824 KB
testcase_01	AC	52 ms 37,028 KB
testcase_02	AC	51 ms 36,992 KB
testcase_03	AC	129 ms 41,432 KB
testcase_04	AC	132 ms 41,500 KB
testcase_05	AC	126 ms 41,388 KB
testcase_06	AC	124 ms 41,028 KB
testcase_07	AC	129 ms 41,616 KB
testcase_08	AC	1,318 ms 107,280 KB
testcase_09	AC	1,320 ms 110,072 KB
testcase_10	AC	1,275 ms 105,296 KB
testcase_11	AC	1,384 ms 107,124 KB
testcase_12	AC	1,301 ms 107,828 KB
testcase_13	AC	1,570 ms 122,452 KB
testcase_14	AC	1,497 ms 109,324 KB
testcase_15	AC	1,466 ms 104,748 KB
testcase_16	AC	1,262 ms 104,444 KB
testcase_17	AC	1,435 ms 103,928 KB
testcase_18	AC	790 ms 100,180 KB
testcase_19	AC	838 ms 97,052 KB
testcase_20	AC	896 ms 99,060 KB
testcase_21	AC	921 ms 98,568 KB
testcase_22	AC	1,046 ms 99,712 KB
testcase_23	AC	1,094 ms 98,920 KB
testcase_24	AC	1,201 ms 94,736 KB
testcase_25	AC	1,576 ms 122,524 KB
testcase_26	AC	1,329 ms 118,492 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package no1xxx;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class No1038 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), Q = ni();
		int[] from = new int[n - 1];
		int[] to = new int[n - 1];
		for (int i = 0; i < n - 1; i++) {
			from[i] = ni() - 1;
			to[i] = ni() - 1;
		}
		int[][] g = packU(n, from, to);
		ConstBombQuery cbq = new ConstBombQuery(g);
		
		for(int z = 0;z < Q;z++) {
			int X = ni()-1, Y = ni(), Z = ni();
			out.println(cbq.get(X));
			cbq.query(X, Y, Z);
		}
	}
	
	public static int[] buildCentroidTree(int[][] g) {
		int n = g.length;
		int[] ctpar = new int[n];
		Arrays.fill(ctpar, -1);
		buildCentroidTree(g, 0, new boolean[n], new int[n], new int[n], new int[n], ctpar);
		return ctpar;
	}
	
	private static int buildCentroidTree(int[][] g, int root, boolean[] sed, int[] par, int[] ord, int[] des, int[] ctpar)
	{
		// parent and level-order
		ord[0] = root;
		par[root] = -1;
		int r = 1;
		for(int p = 0;p < r;p++) {
			int cur = ord[p];
			for(int nex : g[cur]){
				if(par[cur] != nex && !sed[nex]){
					ord[r++] = nex;
					par[nex] = cur;
				}
			}
		}
		// if(r == 1)return;
		
		// DP and find a separator
		int sep = -1; // always exists
		outer:
		for(int i = r-1;i >= 0;i--){
			int cur = ord[i];
			des[cur] = 1;
			for(int e : g[cur]){
				if(par[cur] != e && !sed[e])des[cur] += des[e];
			}
			if(r-des[cur] <= r/2){
				for(int e : g[cur]){
					if(par[cur] != e && !sed[e] && des[e] >= r/2+1)continue outer;
				}
				sep = cur;
				break;
			}
		}
		
		sed[sep] = true;
		for(int e : g[sep]){
			if(!sed[e])ctpar[buildCentroidTree(g, e, sed, par, ord, des, ctpar)] = sep;
		}
		return sep;
	}

	public static long sumFenwick(long[] ft, int i)
	{
		long sum = 0;
		for(i++;i > 0;i -= i&-i)sum += ft[i];
		return sum;
	}
	
	public static void addFenwick(long[] ft, int l, int r, long v)
	{
		addFenwick(ft, l, v);
		addFenwick(ft, r, -v);
	}
	
	public static void addFenwick(long[] ft, int i, long v)
	{
		if(v == 0)return;
		int n = ft.length;
		for(i++;i < n;i += i&-i)ft[i] += v;
	}

	
	public static class ConstBombQuery {
		LCAByEulerTourWithSparseTable lca;
		long[][] vals;
		long[][] valsn;
		int[] cpar;
		
		public ConstBombQuery(int[][] g)
		{
			int n = g.length;
			
			cpar = buildCentroidTree(g);
			vals = new long[n][];
			valsn = new long[n][];
			
			dfsTopCT(cpar, g);
			for(int i = 0;i < n;i++) {
				if(valsn[i] == null)valsn[i] = new long[0];
			}
			
			lca = new LCAByEulerTourWithSparseTable(g, 0);
		}
		
		public long get(int V)
		{
			long ret = 0;
			for(int x = V, pre = -1;x != -1;pre = x, x = cpar[x]) {
				int d = lca.d(x, V);
				ret += sumFenwick(vals[x], d);
				if(pre != -1) {
					ret -= sumFenwick(valsn[pre], d);
				}
			}
			return ret;
		}
		
		public void query(int V, int R, long val)
		{
			for(int x = V, pre = -1;x != -1;pre = x, x = cpar[x]) {
				int d = lca.d(x, V);
				if(d <= R) {
					addFenwick(vals[x], 0, val);
					if(R-d+1 < vals[x].length)addFenwick(vals[x], R-d+1, -val);
					if(pre != -1) {
						addFenwick(valsn[pre], 0, val);
						if(R-d+1 < valsn[pre].length)addFenwick(valsn[pre], R-d+1, -val);
					}
				}
			}
		}
		
		/**
		 * w: 頂点重み
		 * wt: weight table. wt[i] = (頂点iのsepからの重み合計。sepは含まない)
		 * dt: distance table. dt[i] = (頂点iのsepからの距離)
		 * vs: vertices. vssのテンポラリ
		 * vals: vertices. vals[j] = (j番目のneckにある頂点のpreorder)
		 * ctch: children of centroid tree
		 * stack, inds, rulers: テンポラリ
		 * @author uwi
		 *
		 */
		static class Context
		{
			boolean[] seps; // is separator?
			long[] wt; // [ind] = w between sep and ind
			int[] dt;
			int[] vs;
			int[][] vals; // [neckind][vertices]
			int[][] ctch;
			int[][] g;
			int[] stack;
			int[] inds;
			int[] rulers; // temp. [neckp] = separator
			int[] cpar;
		}

		public Context dfsTopCT(int[] cpar, int[][] g) {
			int n = g.length;
			int ctroot = -1;
			for(int i = 0;i < n;i++)if(cpar[i] == -1)ctroot = i;
			
			Context cx = new Context();
			cx.cpar = cpar;
			cx.seps = new boolean[n];
			cx.wt = new long[n];
			cx.dt = new int[n];
			cx.vs = new int[n];
			cx.vals = new int[n][];
			cx.ctch = parentToChildren(cpar);
			cx.g = g;
			cx.stack = new int[n];
			cx.inds = new int[n];
			cx.rulers = new int[n];
			dfs(ctroot, cx);
			return cx;
		}
		
		public static int[][] parentToChildren(int[] par)
		{
			int n = par.length;
			int[] ct = new int[n];
			for(int i = 0;i < n;i++){
				if(par[i] >= 0){
					ct[par[i]]++;
				}
			}
			int[][] g = new int[n][];
			for(int i = 0;i < n;i++){
				g[i] = new int[ct[i]];
			}
			for(int i = 0;i < n;i++){
				if(par[i] >= 0){
					g[par[i]][--ct[par[i]]] = i;
				}
			}
			
			return g;
		}

		private void dfs(int sep, Context cx)
		{
			cx.seps[sep] = true;
			int neckp = 0;
			for(int neck : cx.g[sep]){
				if(cx.seps[neck])continue;
				
				int sp = 0;
				cx.inds[sp] = 0;
//				cx.wt[neck] = w[neck];
				cx.dt[neck] = 1;
				int vsp = 0;
				cx.stack[sp++] = neck;
				while(sp > 0){
					int cur = cx.stack[sp-1];
					if(cx.inds[sp-1] == 0){
						cx.vs[vsp++] = cur;
						if(cx.cpar[cur] == sep)cx.rulers[neckp] = cur;
					}
					if(cx.inds[sp-1] == cx.g[cur].length){
						sp--; 
						continue; 
					}
					int e = cx.g[cur][cx.inds[sp-1]++];
					if(!cx.seps[e] && !(sp-2 >= 0 && e == cx.stack[sp-2])){
//						cx.wt[e] = cx.wt[cur] + w[e];
						cx.dt[e] = sp + 1;
						cx.stack[sp] = e;
						cx.inds[sp] = 0;
						sp++;
					}
				}
				cx.vals[neckp] = Arrays.copyOf(cx.vs, vsp);
				neckp++;
			}
			
			process(sep, cx, Arrays.copyOf(cx.vals, neckp));
			
			for(int e : cx.ctch[sep])dfs(e, cx);
		}
		
		private void process(int sep, Context cx, int[][] vss)
		{
			int maxd = 0;
			for(int i = 0;i < vss.length;i++) {
				int lmaxd = 0;
				for(int v : vss[i]) {
					lmaxd = Math.max(lmaxd, cx.dt[v]);
				}
				valsn[cx.rulers[i]] = new long[lmaxd + 3];
				maxd = Math.max(maxd, lmaxd);
			}
			vals[sep] = new long[maxd + 3];
		}
		
	}
	
	public static class LCAByEulerTourWithSparseTable {
		public EulerTour et;
		public int[][][] st;
		
		public LCAByEulerTourWithSparseTable(int[][] g, int root)
		{
			et = edgedEulerTour(g, root);
			st = buildP(et.deps);
		}
		
		public int lca(int x, int y)
		{
			int lx = et.last[x], ly = et.last[y];
			return et.vs[rmqpos(st, Math.min(lx, ly), Math.max(lx, ly)+1)];
		}
		
		public int d(int x, int y)
		{
			int lx = et.last[x], ly = et.last[y];
			return et.deps[lx] + et.deps[ly] - 2 * rmqval(st, Math.min(lx, ly), Math.max(lx, ly)+1);
		}
		
		public static EulerTour edgedEulerTour(int[][] g, int root)
		{
			int n = g.length;
			int[] vs = new int[2*n-1];
			int[] deps = new int[2*n-1];
			int[] first = new int[n];
			int[] last = new int[n];
			int p = 0;
			
			int[] stack = new int[n];
			int[] inds = new int[n];
			int[] sdeps = new int[n];
			int sp = 0;
			stack[sp++] = root;
			first[root] = -1;
			last[root] = 2*n-2;
			outer:
			while(sp > 0){
				int cur = stack[sp-1], ind = inds[sp-1], sdep = sdeps[sp-1];
				vs[p] = cur;
				deps[p] = sdep;
				p++;
				while(ind < g[cur].length){
					int nex = g[cur][ind++];
					if(sp-2 >= 0 && nex == stack[sp-2])continue;
					inds[sp-1] = ind;
					stack[sp] = nex;
					inds[sp] = 0;
					sdeps[sp] = sdep+1;
					first[nex] = p-1;
					sp++;
					continue outer;
				}
				inds[sp-1] = ind;
				if(cur != root)last[cur] = p-1;
				sp--;
			}
			
			return new EulerTour(vs, first, last, deps);
		}
		
		public static class EulerTour
		{
			public int[] vs; // vertices
			public int[] first; // first appeared time
			public int[] last; // last appeared time
			public int[] deps;
			
			public EulerTour(int[] vs, int[] f, int[] l, int[] deps) {
				this.vs = vs;
				this.first = f;
				this.last = l;
				this.deps = deps;
			}
		}
		
		public static int[][][] buildP(int[] a)
		{
			int n = a.length;
			int b = 32-Integer.numberOfLeadingZeros(n);
			int[][] ret = new int[b][];
			int[][] pos = new int[b][];
			for(int i = 0, l = 1;i < b;i++, l*=2) {
				if(i == 0) {
					ret[i] = a;
					pos[i] = new int[n];
					for(int j = 0;j < n;j++)pos[i][j] = j;
				}else {
					ret[i] = new int[n-l+1];
					pos[i] = new int[n-l+1];
					for(int j = 0;j < n-l+1;j++) {
						if(ret[i-1][j] < ret[i-1][j+l/2]){
							ret[i][j] = ret[i-1][j];
							pos[i][j] = pos[i-1][j];
						}else{
							ret[i][j] = ret[i-1][j+l/2];
							pos[i][j] = pos[i-1][j+l/2];
						}
					}
				}
			}
			return new int[][][]{ret, pos};
		}
		
		public static int rmqpos(int[][][] st, int a, int b)
		{
			int t = 31-Integer.numberOfLeadingZeros(b-a);
			if(st[0][t][a] < st[0][t][b-(1<<t)]){
				return st[1][t][a];
			}else{
				return st[1][t][b-(1<<t)];
			}
		}
		
		public static int rmqval(int[][][] st, int a, int b)
		{
			int t = 31-Integer.numberOfLeadingZeros(b-a);
			if(st[0][t][a] < st[0][t][b-(1<<t)]){
				return st[0][t][a];
			}else{
				return st[0][t][b-(1<<t)];
			}
		}

	}

	public static int[][] parents3(int[][] g, int root) {
		int n = g.length;
		int[] par = new int[n];
		Arrays.fill(par, -1);

		int[] depth = new int[n];
		depth[0] = 0;

		int[] q = new int[n];
		q[0] = root;
		for (int p = 0, r = 1; p < r; p++) {
			int cur = q[p];
			for (int nex : g[cur]) {
				if (par[cur] != nex) {
					q[r++] = nex;
					par[nex] = cur;
					depth[nex] = depth[cur] + 1;
				}
			}
		}
		return new int[][] { par, q, depth };
	}

	static int[][] packU(int n, int[] from, int[] to) {
		int[][] g = new int[n][];
		int[] p = new int[n];
		for (int f : from)
			p[f]++;
		for (int t : to)
			p[t]++;
		for (int i = 0; i < n; i++)
			g[i] = new int[p[i]];
		for (int i = 0; i < from.length; i++) {
			g[from[i]][--p[from[i]]] = to[i];
			g[to[i]][--p[to[i]]] = from[i];
		}
		return g;
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new No1038().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

yukicoder

結果

テストケース

ソースコード