import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; class Edge{ int src,dst; long cost; public Edge(int src_,int dst_,long cost_) { src=src_; dst=dst_; cost=cost_; } } class BIT{ int n; long[] a; public BIT(int n) { this.n=n; a=new long[n+1]; } void add(int k,long v) { for(++k;k<=n;k+=k&-k) a[k]+=v; } long _sum(int k) { long ret=0; for(++k;k>0;k-=k&-k) ret+=a[k]; return ret; } long sum(int l,int r) { return _sum(r-1)-_sum(l-1); } } public class Main implements Runnable{ public static void main(String[] args) { new Thread(null,new Main(), "" ,Runtime.getRuntime().maxMemory()).start(); } int pointer=0; void dfs(int cur,int par,ArrayList[] g,long[] base,int[] depth,int[] in,int[] out) { in[cur]=pointer++; for(Edge e:g[cur]) { if(e.dst==par)continue; base[e.dst]=base[cur]+e.cost; depth[e.dst]=depth[cur]+1; dfs(e.dst,cur,g,base,depth,in,out); } out[cur]=pointer; } public void run() { FastScanner sc=new FastScanner(); PrintWriter pw=new PrintWriter(System.out); int N=sc.nextInt(); ArrayList[] g=new ArrayList[N]; long[] base=new long[N]; int[] depth=new int[N]; long[] A=new long[N]; int[] in=new int[N]; int[] out=new int[N]; BIT bit0=new BIT(N); BIT bit1=new BIT(N); for(int i=0;i(); for(int i=0;i Integer.MAX_VALUE) throw new NumberFormatException(); return (int) nl; } public double nextDouble() { return Double.parseDouble(next());} }