"The Story of a Tree" solved using depth-first search
gcd is missing a docstring.
gcd is tail-recursive, but Python doesn't have tail-recursion elimination, and so:

&gt;&gt;&gt; gcd(3**7000, 2**10000)
Traceback (most recent call last):
  File "&lt;stdin&gt;", line 1, in &lt;module&gt;
[...]
RecursionError: maximum recursion depth exceeded


It is more robust to turn the tail-recursion into a loop:

def gcd(a, b):
    """Return the greatest common divisor of a and b."""
    while b:
        a, b = b, a % b
    return a


and then:

&gt;&gt;&gt; gcd(3**7000, 2**10000)
1

Python has a built-in greater common divisor function, fractions.gcd, so you could use that and avoid writing your own.
The only use for gcd is to print a fraction in lowest terms. The built-in fractions.Fraction class can do that, so you could write:

from fractions import Fraction
print("{0.numerator}/{0.denominator}".format(Fraction(win, n)))

The names dfs1 and dfs2 are not very informative. Sure, they do some kind of depth-first search, but which one is which?
The docstrings for dfs1 and dfs2 don't explain the arguments m, guess, seen, cost, and k. What am I supposed to pass for these arguments?
The seen argument to dfs1 and dfs2 always gets an empty set which is not used again after the function returns. So it would better for these functions to use a local variable and initialize it with an empty set. Then there would be no risk of passing the wrong value for this argument.
Instead of creating an empty list and appending an item to it:

stack = []
stack.append(root)


it's simpler to create a list with one item:

stack = [root]

Instead of testing the length of a list:

while len(stack):


it's simpler to test the list itself:

while stack:

Instead of computing the index of the last element of a list:

root = stack.pop(len(stack)-1)


you can use a negative index:

root = stack.pop(-1)


but by default the pop method pops the last element, so you can write:

root = stack.pop()

Instead of writing this complex condition:

count += (1 if root in guess and i in guess[root] else 0)


you can take advantage of the fact that True equals 1 and False equals 0, and write:

count += root in guess and i in guess[root]

The only use you make of guess is to test if it contains a directed edge. But this is slightly awkward because the test takes two steps. It would be better if you built a data structure that was better adapted to the use you intend to make of it. In this case, you could build a set of directed edges. So instead of:

guess = {}
for a1 in xrange(g):
    u,v = raw_input().strip().split(' ')
    u,v = [int(u),int(v)]
    if u not in guess:
        guess[u] = []
    guess[u].append(v)


write:

guess = set()
for _ in range(g):
    u, v = map(int, raw_input().split())
    guess.add((u, v))


and then in dfs1 you can write:

count += (root, i) in guess


(The construction of guess can be turned into a set comprehension, like this:

guess = {tuple(map(int, raw_input().split())) for _ in range(g)}


but I think the explicit loop is a bit clearer.)
Similarly, in dfs2 you have the complicated expression:

stack.append((i, cost - (1 if root in guess and i in guess[root] else 0) + (1 if i in guess and root in guess[i] else 0)))


Given the set of directed edges, this simplifies to:

stack.append((i, cost - ((root, i) in guess) + ((i, root) in guess)))

The top-level code is hard to test, because you can't call it from a Python program or the interactive interpreter. Better to put it in its own function, conventionally called main.
The top-level code is full of one-letter variables (m, q, g, k, u, v). It is hard to guess what these mean. Although it makes sense to stick with the names from the HackerRank problem description, a comment or two would help remind the reader of what they mean.
When you don't use a loop variable like a1, it's conventional to use the name _.
Some of the repetition in the input code can be avoided by using collections.defaultdict:

# Map from node to list of neighbours.
tree = defaultdict(list)
for _ in range(n - 1):
    u, v = map(int, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)