// 2023.04.15 at 22:05:25 HKT import java.io.BufferedInputStream import java.io.File import java.io.PrintWriter import kotlin.system.measureTimeMillis import java.util.TreeMap import java.util.TreeSet import kotlin.random.Random import kotlin.random.nextInt // 1. Modded const val p = 1000000007L const val pI = p.toInt() fun Int.adjust():Int{ if(this >= pI){ return this - pI }else if (this < 0){ return this + pI };return this } fun Int.snap():Int{ if(this >= pI){return this - pI} else return this} infix fun Int.mm(b:Int):Int{ return ((this.toLong() * b) % pI).toInt() } infix fun Int.mp(b:Int):Int{ val ans = this + b;return if(ans >= pI) ans - pI else ans } infix fun Int.ms(b:Int):Int{ val ans = this - b;return if(ans < 0) ans + pI else ans } fun Int.inverse():Int = intPow(this,pI-2,pI) infix fun Int.modDivide(b:Int):Int{ return this mm (b.inverse()) } fun intPow(x:Int,e:Int,m:Int):Int{ var X = x ; var E =e ; var Y = 1 while(E > 0){ if(E and 1 == 0){ X = ((1L * X * X) % m).toInt() E = E shr 1 }else{ Y = ((1L * X * Y) % m).toInt() E -= 1 } } return Y } // 2. DP initial values const val plarge = 1_000_000_727 const val nlarge = -plarge const val phuge = 2_727_000_000_000_000_000L const val nhuge = -phuge // 3. convenience conversions val Boolean.chi:Int get() = if(this) 1 else 0 //characteristic function val BooleanArray.chiarray:IntArray get() = IntArray(this.size){this[it].chi} val Char.code :Int get() = this.toInt() - 'a'.toInt() //3. hard to write stuff fun IntArray.put(i:Int,v:Int){ this[i] = (this[i] + v).adjust() } val mint:MutableList get() = mutableListOf() val mong:MutableList get() = mutableListOf() val mchar:MutableList get() = mutableListOf() //4. more outputs fun List.conca():String = this.joinToString("") val CharArray.conca :String get() = this.joinToString("") val IntArray.conca :String get() = this.joinToString(" ") @JvmName("concaInt") fun List.conca():String = this.joinToString(" ") val LongArray.conca:String get() = this.joinToString(" ") @JvmName("concaLong") fun List.conca():String = this.joinToString(" ") //5. Pair of ints const val longmask = (1L shl 32) - 1 fun makepair(a:Int, b:Int):Long = (a.toLong() shl 32) xor (longmask and b.toLong()) val Long.first get() = (this ushr 32).toInt() val Long.second get() = this.toInt() //6. strings val String.size get() = this.length const val randCount = 100 //7. bits fun Int.has(i:Int):Boolean = (this and (1 shl i) != 0) fun Long.has(i:Int):Boolean = (this and (1L shl i) != 0L) //8 TIME inline fun TIME(f:()->Unit){ val t = measureTimeMillis(){ f() } println("$t ms") } //9.ordered pair fun order(a:Int, b:Int):Pair{ return Pair(minOf(a,b), maxOf(a,b)) } //10 rand fun rand(x:Int) = Random.nextInt(x) fun rand(x:IntRange) = Random.nextInt(x) val coin:Boolean get() = Random.nextBoolean() //11 typing issues, rename typealias ints = IntArray typealias longs = LongArray typealias bools = BooleanArray typealias pii = Pair const val interactive = false object Reader{ private const val BS = 1 shl 16 private const val NC = 0.toChar() private val buf = ByteArray(BS) private var bId = 0 private var size = 0 private var c = NC var warningActive = true var fakein = StringBuilder() private var IN: BufferedInputStream = BufferedInputStream(System.`in`, BS) val OUT: PrintWriter = PrintWriter(System.out) private val char: Char get() { if(interactive){ return System.`in`.read().toChar() } while (bId == size) { size = IN.read(buf) // no need for checked exceptions if (size == -1) return NC bId = 0 } return buf[bId++].toChar() } fun nextInt(): Int { var neg = false if (c == NC) c = char while (c < '0' || c > '9') { if (c == '-') neg = true c = char } var res = 0 while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0') c = char } return if (neg) -res else res } fun nextLong(): Long { var neg = false if (c == NC) c = char while (c < '0' || c > '9') { if (c == '-') neg = true c = char } var res = 0L while (c in '0'..'9') { res = (res shl 3) + (res shl 1) + (c - '0') c = char } return if (neg) -res else res } fun nextString():String{ val ret = StringBuilder() while (true){ c = char if(!isWhitespace(c)){ break} } ret.append(c) while (true){ c = char if(isWhitespace(c)){ break} ret.append(c) } return ret.toString() } fun isWhitespace(c:Char):Boolean{ return c == ' ' || c == '\n' || c == '\r' || c == '\t' } fun rerouteInput(){ if(warningActive){ put("Custom test enabled") println("Custom test enabled") warningActive = false } val S = fakein.toString() println("New Case ") println(S.take(80)) println("...") fakein.clear() IN = BufferedInputStream(S.byteInputStream(),BS) } fun flush(){ OUT.flush() } fun takeFile(name:String){ IN = BufferedInputStream(File(name).inputStream(),BS) } } fun eat(){ val st1 = TreeSet(); val st2 = TreeMap()} fun put(aa:Any){ Reader.OUT.println(aa) if(interactive){ Reader.flush()} } fun put(vararg x:Any){ for(c in x){ Reader.OUT.print(c) Reader.OUT.print(" ") } Reader.OUT.print("\n") if(interactive){ Reader.flush()} } fun done(){ Reader.OUT.close() } fun share(aa:Any){ Reader.fakein.append(format(aa)) Reader.fakein.append("\n") } val getintfast:Int get() = Reader.nextInt() val getint:Int get(){ val ans = getlong ; if(ans > Int.MAX_VALUE) IntArray(1000000000); return ans.toInt() } val getlong:Long get() = Reader.nextLong() val getstr:String get() = Reader.nextString() fun getline(n:Int):IntArray{ return IntArray(n){getint} } fun getlineL(n:Int):LongArray{ return LongArray(n){getlong} } fun subformat(a:Any?):String{ // for not a collection return if(a == null) "null" else if(a is Iterable<*> ) a.joinToString(" ") else if(a is BooleanArray) a.joinToString("") { if (it) "1" else "0" } else if(a is IntArray) a.joinToString(" ") else if(a is LongArray) a.joinToString(" ") else a.toString() } fun format(a:Any?):String { if (a == null) { return "null" } else if (a is BooleanArray) { return a.joinToString("") { if (it) "1" else "0" } } else if (a is Array<*>) { return "\n"+a.joinToString("\n"){subformat(it)} } else { return subformat(a)} } var dmark = -1 infix fun Any.dei(a:Any?){ dmark++ ; debug() println("<${dmark}> ${this} : ${format(a)}") } const val just = " " fun crash(){ throw Exception("Bad programme")} fun assert(a:Boolean){ if(!a){ throw Exception("Failed Assertion") }} enum class solveMode { real, rand, tc } object solve{ var mode:solveMode = solveMode.real var tcNum:Int = 0 var rand:()->Unit = {} var TC:MutableMapUnit> = mutableMapOf() var tn:Long = 0 fun cases(onecase:()->Unit){ val t = if(mode == solveMode.real){if(singleCase) 1 else getint} else if(mode == solveMode.tc){1 } else randCount if(pI != 998_244_353 && pI != 1_000_000_007){ throw Exception("Not usual primes!") } if(t == 1 && mode != solveMode.real){ tn = System.currentTimeMillis() } repeat(t){ if(mode == solveMode.tc){ TC[tcNum]?.let { it() } Reader.rerouteInput() }else if(mode == solveMode.rand){ rand() Reader.rerouteInput() } onecase() } if(t == 1 && mode != solveMode.real){ val dt = System.currentTimeMillis() - tn println("Time $dt ms ") } } fun rand(a:()->Unit){ this.rand = a } fun tc(id:Int = 0,a:()->Unit){ TC[id] = a } fun usetc(a:Int = 0 ){ this.tcNum = a this.mode = solveMode.tc } fun userand(){ this.mode = solveMode.rand } } fun debug(){} const val graphWeighed = false class Graph(val n:Int, val m:Int, val directed:Boolean) { val maxedge = if (directed) m else m * 2 var cnt = -1 val edgecount:Int get() = cnt + 1 val next = IntArray(maxedge) val head = IntArray(n) { -1 } val to = IntArray(maxedge) val from = IntArray(maxedge) val weights = IntArray(if (graphWeighed) m else 0) val Q = fastDeque(0,n) private fun primitive_add(u: Int, v: Int): Int { next[++cnt] = head[u] head[u] = cnt to[cnt] = v from[cnt] = u return cnt } fun add(u: Int, v: Int): Int { val e = primitive_add(u, v) if (!directed) { primitive_add(v, u) } return if (directed) e else e shr 1 } fun addWeighted(u: Int, v: Int, w: Int):Int{ val e = add(u, v) weights[e] = w return e } //Basic Transversals inline fun NS(a:Int, act:(Int)->Unit){ var i= head[a] while(i != -1){ act(to[i]) i = next[i] } } inline fun NS_E(a:Int, act:(e:Int,v:Int)->Unit){ var i= head[a] while(i != -1){ act(i,to[i]) i = next[i] } } inline fun everyEdge(act:(a:Int, b:Int)->Unit){ val s = if(directed) 1 else 2 for(e in 0 until edgecount step s ){ act(from[e], to[e]) } } inline fun everyDirectedEdge(act:(a:Int, b:Int)->Unit){ for(e in 0 until edgecount){ act(from[e], to[e]) } } // Store a spanning tree, var root = 0 var preorder:IntArray = IntArray(0) var parent:IntArray = IntArray(0) val hasDFSorder:Boolean get() = preorder.size == n var parentEdge:IntArray = IntArray(0) //stores the order fun treeOrderDFS(withEdges:Boolean = false){ parent = IntArray(n){-1} var pt = -1 preorder = IntArray(n){-1} if(withEdges) parentEdge = IntArray(n){-1} Q.reset() // val Q = fastDeque(0,n) parent[root] = root Q.addLast(root) while(Q.isNotEmpty()){ val a = Q.removeLast() val p = parent[a] preorder[++pt] = a NS_E(a){e,v -> if(v == p) return@NS_E if(withEdges) parentEdge[v] = if(directed) e else (e shr 1) parent[v] = a Q.addLast(v) } } } inline fun BFS(distRoot:Int, reached:(Int, Int)->Unit = {_,_ ->}): IntArray { Q.reset() val explored = IntArray(n+1){-1} // also store parents Q.addLast(distRoot) explored[distRoot] = -2 val dist = IntArray(n){-1} dist[distRoot] = 0 while(Q.size > 0){ val x = Q.removeFirst() reached(x,explored[x]) NS(x){ a-> if(explored[a] == -1){ explored[a] = x dist[a] = dist[x] + 1 Q.addLast(a) } } } return dist } inline fun trueOrderDFS(root:Int?,newroot:(r:Int) ->Unit, preexplore:(v:Int) ->Unit, postExplore:(v:Int)->Unit, move:(p:Int,v:Int,e:Int)->Unit, cross:(from:Int, to:Int,e:Int)->Unit ){ Q.reset() val explored = BooleanArray(n){false} val headHere = head.copyOf() for(i in 0 until n) { if (explored[i] || (root != null && root != i)) continue newroot(i) explored[i] = true Q.addLast(i) while(Q.isNotEmpty()){ val v = Q.last() val e = headHere[v] if(e == head[v]){ preexplore(v) } if(e == -1){ postExplore(v) Q.removeLast() continue } headHere[v] = next[e] val t = to[e] if(!explored[t]){ explored[t] = true move(v,t,e) Q.addLast(t) }else{ cross(v,t,e) } } } } fun EulerDoubleOrder(): Pair { var pointer = -1 val euler = IntArray(2 * n - 1) val entry = IntArray(n) fun dfs(v:Int, p:Int) { euler[++pointer] = v entry[v] = pointer NS(v){ w-> if(w == p) return@NS dfs(w,v) euler[++pointer] = v } } dfs(root,-1) return Pair(euler, entry) } //Tree Transversals inline fun leafFirst(act:(Int)->Unit){ if(!hasDFSorder) treeOrderDFS() for(i in preorder.lastIndex downTo 0){ act(preorder[i]) } } inline fun rootFirst(act:(Int)->Unit){ if(!hasDFSorder) treeOrderDFS() for(a in preorder){ act(a) } } inline fun rootFirstEdge(act:(from:Int, to:Int, e:Int)->Unit){ if(!hasDFSorder) treeOrderDFS(true) for(i in 1 until preorder.size){ val v = preorder[i] act(parent[v],v,parentEdge[v]) } } // Basic invariants maintaining fun calculateParents():IntArray{ if(!hasDFSorder) treeOrderDFS() return parent } fun calculateSizes():IntArray{ val ret = IntArray(n){1} leafFirst { v -> if(v != root) ret[parent[v]] += ret[v] } return ret } fun calculateSubtreeSum(weights:IntArray){ leafFirst { v -> if(v != root) weights[parent[v]] += weights[v] } } fun calculateDepth(): IntArray { val ret = IntArray(n) rootFirst { v -> if(v != root) ret[v] = ret[parent[v]] + 1 } return ret } inline fun subs(v:Int, act:(Int)->Unit){ NS(v){w -> if(w != parent[v]) act(w) } } fun calculateDepthWeighted(): LongArray { val ret = LongArray(n) rootFirstEdge{from,to,e -> ret[to] = ret[from] + weights[e]} return ret } fun outdegree():IntArray{ val ret = IntArray(n) everyDirectedEdge { a, b -> ret[a] ++ } return ret } fun indegree():IntArray{ val ret = IntArray(n) everyDirectedEdge {a, b -> ret[b] ++} return ret } fun degree():IntArray = outdegree() fun reversed():Graph{ assert(directed) val new = Graph(n,m,true) everyDirectedEdge { a, b -> new.add(b,a) } return new } fun intime():IntArray{ val tin = IntArray(n) if(!hasDFSorder) treeOrderDFS() for(i in 0 until n) tin[preorder[i]] = i return tin } fun outtime():IntArray{ val tout = intime() leafFirst { v -> val p = parent[v] if(p == v) return@leafFirst tout[p] = maxOf(tout[p], tout[v]) } return tout } fun markcomponent():IntArray{ val ret = IntArray(n) rootFirst { v -> if(v == root) return@rootFirst if(parent[v] == root){ ret[v] = v; return@rootFirst} ret[v] = ret[parent[v]] } return ret } } private typealias ei = Int private typealias earr = IntArray //NOT batle tested class fastDeque(val l:Int, val r:Int) { val total = r - l + 1 val st = earr(total) var startpointer = 0 - l var endpointer = startpointer - 1 val size: Int get() = endpointer - startpointer + 1 val lastIndex:Int get() = endpointer fun reset(){ startpointer = -l endpointer = startpointer -1 } fun isEmpty(): Boolean { return endpointer < startpointer } fun isNotEmpty():Boolean{ return endpointer >= startpointer } fun first():ei{ assert(isNotEmpty()) return st[startpointer] } fun last():ei{ assert(isNotEmpty()) return st[endpointer] } fun addFirst(v:ei ){ startpointer -- st[startpointer]= v } fun addLast(v:ei){ endpointer ++ st[endpointer] = v } fun removeFirst(): ei { assert(isNotEmpty()) val ret = st[startpointer] startpointer ++ return ret } fun removeLast(): ei { assert(isNotEmpty()) val ret = st[endpointer] endpointer -- return ret } fun toArray():earr{ return st.sliceArray(startpointer..endpointer) } fun toList():List{ return st.slice(startpointer..endpointer) } inline fun forEach(act:(v:ei)->Unit){ for(i in startpointer..endpointer){ act(st[i]) } } inline fun withIndex(act:(i:Int,v:ei)->Unit){ for(i in startpointer..endpointer){ act(i-startpointer,st[i]) } } operator fun get(v:Int): ei { return st[startpointer + v] } } fun fastEmptyList(max:Int):fastDeque{ return fastDeque(0,max-1) } const val singleCase = false fun Graph.strong_reroot():LongArray { val sizes = IntArray(n) val dist = LongArray(n) val root = 0 fun Graph.first_dfs(v:Int, p:Int){ sizes[v] = 1 NS(v){ w-> if(w == p){ return@NS } first_dfs(w,v) sizes[v] += sizes[w] dist[v] += dist[w] + sizes[w] } } first_dfs(root,-1) fun root_change(from:Int, to:Int){ dist[from] -= dist[to] + sizes[to] sizes[from] -= sizes[to] sizes[to] += sizes[from] dist[to] += dist[from] + sizes[from] } val finaldist = LongArray(n) fun reroot_dfs(v:Int, p:Int){ finaldist[v] = dist[v] //everything correct here NS(v){ u -> // for each neighbour u of v if(u == p) return@NS root_change(v,u) reroot_dfs(u,v) root_change(u,v) } } reroot_dfs(root,-1) return finaldist } fun choose2(x:Int):Long{ return (x).toLong() * (x-1) /2L } var tc = 0 fun gon(a:Any){ tc++ put("Case #${tc}: $a") } fun Double.tocleanstring():String{ return this.toBigDecimal().toPlainString() } fun main(){ solve.cases{ val w = getint val e = getint val c = getint val G = Graph(w,w-1,false) repeat(w-1){ G.add(it ,getint-1) } val H = Graph(e,e-1,false) repeat(e-1){ H.add( it, getint - 1) } val gd = G.strong_reroot() val hd = H.strong_reroot() val count = choose2(w + e ) // val left = choose2(w) // val right = choose2(e) val middle = w * e.toLong() val leftsum = gd.sum() / 2L val rightsum = hd.sum() / 2L val ans = mutableListOf() repeat(c){ val l = getint -1 val r = getint -1 val A = gd[l] * e val B = hd[r] * w val totalvalue = leftsum + rightsum + (A + B + middle) ans.add(totalvalue.toDouble() / count) } gon(ans.map { it.tocleanstring() }.joinToString(" ")) } done() }