O(nk) solution won't pass in Python because of it's high overhead.

Here's the same algorithm in Java:

static int tree[][];
static int k;
static long answer;

void main() {
	tree = getTree(); // tree[i] -> list of neighbors of vertex i
	k = getK();
	answer = 0;
	dfs(0, -1, 0);
	System.out.println(answer);
}

Map<Integer, Integer> dfs(int vertex, int parent, int depth) {
	Map<Integer, Integer> result = new HashMap<Integer, Integer>();
	// Counts the number vertices having every depth from depth to depth+k, exclusive.
	// Size is at most k, and it is not greater than the size of the subtree.
	result.put(depth, 1); // Count the root vertex.
	for (int child: tree[vertex]) {
		if (child == parent) {
			continue;
		}
		Map<Integer, Integer> result2 = dfs(child, vertex, depth + 1);
		// Now, merge the smaller map into the larger one.
		// This way, each vertex is merged at most log(n) times.
		// Actually, each vertex is merged at most log(k) times
		// while it belongs to subtrees of size at most k.
		// This adds n*log(k) to the complexity.
		// Also, there are at most n/k merges of subtrees having
		// both size at least k, and each of them costs at most O(k),
		// which adds O(n) to the complexity.
		if (result.size() < result2.size()) {
			Map<Integer, Integer> tmp = result;
			result = result2;
			result2 = tmp;
		}
		// This loop updates the answer.
		for (Entry<Integer, Integer> e: result2.entrySet()) {
			int firstDepth = e.getKey();
			int secondDepth = 2 * depth + k - firstDepth;
			if (result.containsKey(secondDepth)) {
				answer += (long) result.get(secondDepth) * e.getValue();
			}
		}
		// This loop updates the map.
		for (Entry<Integer, Integer> e: result2.entrySet()) {
			int eDepth = e.getKey();
			if (result.containsKey(eDepth)) {
				result.put(eDepth, result.get(eDepth) + e.getValue());
			} else {
				result.put(eDepth, e.getValue());
			}
		}
	}
	// To keep the size at most k, remove this element.
	// It's too deep to be used any more.
	result.remove(depth + k);
	return result;
}

N*log(N) with a simple idea (1353450, from "vvi graph");

It's correct that single request on level P can result in 4 requests on level p-1, but this means all 4 requests on level p-1 are non-trivial. That is, No more non-trivial requests on level p-1. Linear time complexity still hold.

If you dont understand, think why a interval on a segment tree can be divided into two intervals on next level, but its time complexity is O(h),not O(2^h), where h is the height of segment tree.(at most two non-trivial intervals on each level.)

(Sorry for my poor expression...As a Chinese,I'm not a native speaker of English.)

It's a bit different as compared to what you wrote.

The overall amount of vertices in v's subtree on depth (k-x) is d[v][k-x]. We should not count the vertices that are in u's subtree though, because in this case we are looking only at the paths that would go through v. So we have to subtract that amount, which is d[u][k-x-1]. The (-1) here is because u is exactly one level below v.