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= Meguru.MOD) { sum -= Meguru.MOD; } } io.println(sum); } } io.flush(); } } //be careful for stack overflow class Graph { int n; ArrayList[] edge; @SuppressWarnings("unchecked") public Graph(int n) { this.n = n; edge = new ArrayList[n]; for(int i=0;i(); } } 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[] 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(); } 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 queryDirectionSensitive(int first,int last) { ArrayList head = new ArrayList<>(); ArrayList 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(int u,int v) { ArrayList 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=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 data = new ArrayList<>(); for(int i=0;i 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