MickeyIsAwesome's blog

By MickeyIsAwesome, history, 13 months ago, In English

Problem is as follows ->

A tree is a connected graph that doesn't contain any cycles.

The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.

You are given a tree with n vertices and a positive number k. Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.

Constraints -> 1 ≤ n ≤ 50000, 1 ≤ k ≤ 500 , Edges 1 ≤ ai, bi ≤ n.

161D - Расстояние в дереве

This is my submission -> 229435063

I think my time complexity is O(2*n*k), which is approximately 5*10^7 operations, which should work.

Any help would be appreciated :)

Edit :- I got accepted when I use language as GNU C++14 , instead of GNU C++20 (64) , although it's still on the edge of time limit. Can anyone explain why this issue could've happened?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it