package no399; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; 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 * 1024 * 100).start(); } @Override public void run() { IO io = new IO(); int n = io.nextInt(); Graph g = new Graph(n); for(int i=0;i al = hld.query(io.nextInt()-1, io.nextInt()-1); long sum = 0; for(Query q: al) { int id = q.pathId; int begin = q.first; int end = q.last + 1; sst[id].accumulate(begin, end, 1); sum += sst[id].sum(begin, end); } ans += sum; } System.out.println(ans); } } class RangeAddRangeSum { private int n; private BIT[] bit = new BIT[2]; public RangeAddRangeSum(int size) { this.n = size; for(int i=0;i<2;i++) { bit[i] = new BIT(size+1); } } public void accumulate(int begin,int end,long x) { bit[0].accumulate(begin+1, - x * begin); bit[1].accumulate(begin+1, x); bit[0].accumulate(end+1 , x * end); bit[1].accumulate(end+1 , - x); } private long sum(int i) { return bit[0].sum(i) + bit[1].sum(i) * i; } public long sum(int begin,int end) { return sum(end) - sum(begin); } public String toString() { long[] a = new long[n]; for(int i=0;i0) { s+=bit[i]; i-=i&-i; } return s; } } } //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); } 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 query(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 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; boolean flip; public Query(int pathId,int first,int last) { this.pathId = pathId; if (first < last) { this.first = first; this.last = last; }else{ this.first = last; this.last = first; flip = true; } } public String toString() { return pathId + ":[" + first + "," + last + "]"; } } class IO extends PrintWriter { private final InputStream in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; public IO() { this(System.in);} public IO(InputStream source) { super(System.out); this.in = source;} 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;} private static boolean isNewLine(int c) { return c == '\n' || c == '\r';} public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();} public boolean hasNextLine() { while(hasNextByte() && isNewLine(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 char[] nextCharArray(int len) { if (!hasNext()) { throw new NoSuchElementException(); } char[] s = new char[len]; int i = 0; int b = readByte(); while(isPrintableChar(b)) { if (i == len) { throw new InputMismatchException(); } s[i++] = (char) b; b = readByte(); } return s; } public String nextLine() { if (!hasNextLine()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(!isNewLine(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 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