結果

問題 No.899 γatheree
コンテスト
ユーザー 37zigen
提出日時 2020-08-27 10:30:38
言語 Java
(openjdk 23)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,266 bytes
コンパイル時間 2,737 ms
コンパイル使用メモリ 80,300 KB
実行使用メモリ 79,276 KB
最終ジャッジ日時 2024-11-07 15:32:35
合計ジャッジ時間 13,421 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 7 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	class Seg {
		int n=1;
		long[] v;
		boolean[] clear;
		
		public Seg(int n_) {
			while (n<n_) n*=2;
			v=new long[2*n-1];
			clear=new boolean[2*n-1];
		}
		
		void propagate(int k) {
			if (!clear[k]) return;
			v[k]=0;
			if (2*k+1<2*n-1) {
				clear[2*k+1]=true;
				clear[2*k+2]=true;
			}
			clear[k]=false;
		}
		
		void range_clear(int a,int b) {
			range_clear(0,n,a,b,0);
		}
		
		void range_clear(int l,int r,int a,int b,int k) {
			propagate(k);
			if (r<=a||b<=l) return;
			if (a<=l&&r<=b) {
				clear[k]=true;
				propagate(k);
			} else {
				range_clear(l,(l+r)/2,a,b,2*k+1);
				range_clear((l+r)/2,r,a,b,2*k+2);
				v[k]=v[2*k+1]+v[2*k+2];
			}
		}
		
		long point_add(int a,int b,long add) {
			return point_add(0,n,a,b,0,add);
		}
		
		long point_add(int l,int r,int a,int b,int k,long add) {
			propagate(k);
			if (r<=a||b<=l) return 0;
			if (a<=l&&r<=b) {
				v[k]+=add;
				return v[k];
			} else {
				long vl=point_add(l,(l+r)/2,a,b,2*k+1,add);
				long vr=point_add((l+r)/2,r,a,b,2*k+2,add);
				v[k]=v[2*k+1]+v[2*k+2];
				return vl+vr;
			}
		}
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		ArrayList<Integer>[] g=new ArrayList[N];
		for (int i=0;i<N;++i) g[i]=new ArrayList<>();
		for (int i=0;i<N-1;++i) {
			int u=sc.nextInt();
			int v=sc.nextInt();
			g[u].add(v);
			g[v].add(u);
		}
		int[] ord=new int[N];
		int[] par=new int[N];
		int[] dep=new int[N];
		int[] L1=new int[N];
		int[] R1=new int[N];
		int[] L2=new int[N];
		int[] R2=new int[N];
		{
			for (int i=0;i<N;++i) {
				L2[i]=N;
				R2[i]=-1;
			}
			Arrays.fill(ord, -1);
			Arrays.fill(par, -1);
			ArrayDeque<Integer> dq=new ArrayDeque<>();
			dq.add(0);
			int p=0;
			ord[0]=p++;
			while (!dq.isEmpty()) {
				int cur=dq.pollFirst();
				L1[cur]=p;
				for (int dst:g[cur]) if (dst!=par[cur]) {
					dq.addLast(dst);
					ord[dst]=p++;
					par[dst]=cur;
					dep[dst]=dep[cur]+1;
				}
				R1[cur]=p;
			}
			for (int i=0;i<N;++i) {
				if (dep[i]>=1) {
					L2[par[i]]=Math.min(L2[par[i]], L1[i]);
					R2[par[i]]=Math.max(R2[par[i]], R1[i]);
				}
			}
		}
		long[] A=new long[N];
		for (int i=0;i<N;++i) A[i]=sc.nextLong();
		Seg seg=new Seg(N);
		for (int i=0;i<N;++i) seg.point_add(ord[i], ord[i]+1, A[i]);
		int Q=sc.nextInt();
		PrintWriter pw=new PrintWriter(System.out);
		while (Q-->0) {
			int x=sc.nextInt();
			long add=seg.point_add(L1[x],R1[x],0)+seg.point_add(L2[x],R2[x],0);
			seg.range_clear(L1[x],R1[x]);
			seg.range_clear(L2[x],R2[x]);
			if (dep[x]>=2) {
				add+=seg.point_add(ord[par[par[x]]],ord[par[par[x]]]+1,0);
				seg.range_clear(ord[par[par[x]]],ord[par[par[x]]]+1);
			}
			if (dep[x]>=1) {
				add+=seg.point_add(ord[par[x]],ord[par[x]]+1,0);
				seg.range_clear(ord[par[x]],ord[par[x]]+1);
				add+=seg.point_add(L1[par[x]],R1[par[x]],0);
				seg.range_clear(L1[par[x]],R1[par[x]]);
			}
			seg.point_add(ord[x],ord[x]+1,add);
			pw.println(seg.point_add(ord[x],ord[x]+1,0));
		}
		pw.flush();
	}
	
	void tr(Object...o) {System.out.println(Arrays.deepToString(o));}
}
0