結果

問題 No.899 γatheree
コンテスト
ユーザー 37zigen
提出日時 2020-08-27 10:26:23
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,156 ms / 2,000 ms
コード長 5,439 bytes
コンパイル時間 2,816 ms
コンパイル使用メモリ 81,016 KB
実行使用メモリ 69,900 KB
最終ジャッジ日時 2024-11-07 15:31:33
合計ジャッジ時間 24,905 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    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;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(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 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 double nextDouble() { return Double.parseDouble(next());}
}


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() {
		FastScanner sc = new FastScanner();
		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]) continue;
					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