We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Kitty's Calculations on a Tree
Kitty's Calculations on a Tree
Sort by
recency
|
63 Discussions
|
Please Login in order to post a comment
from collections import Counter, defaultdict
MOD = 10**9 + 7
def read_row(): return (int(x) for x in input().split())
def mul(x, y): return (x * y) % MOD
def add(*args): return sum(args) % MOD
def sub(x, y): return (x - y) % MOD
n, q = read_row()
Construct adjacency list of the tree
adj_list = defaultdict(list)
for _ in range(n - 1): u, v = read_row() adj_list[u].append(v) adj_list[v].append(u)
Construct element to set mapping {element: [sets it belongs to]}
elements = {v: set() for v in adj_list}
for set_no in range(q): read_row() for x in read_row(): elements[x].add(set_no)
Do BFS to find parent for each node and order them in reverse depth
root = next(iter(adj_list)) current = [root] current_depth = 0 order = [] parent = {root: None} depth = {root: current_depth}
while current: current_depth += 1 order.extend(current) nxt = [] for node in current: for neighbor in adj_list[node]: if neighbor not in parent: parent[neighbor] = node depth[neighbor] = current_depth nxt.append(neighbor)
Process nodes in the order created above
score = Counter()
{node: {set_a: [depth, sum of nodes, flow]}}
state = {} for node in reversed(order): states = [state[neighbor] for neighbor in adj_list[node] if neighbor != parent[node]] largest = {s: [depth[node], node, 0] for s in elements[node]}
print(*(score[i] for i in range(q)), sep='\n')
I was able to find some useful hints in the discussions, but they're buried below a mountain of misinformation and nonfunctional solutions. So if you're looking for help, here are the basic components of the solution (or at least, of a solution).
I'm not sure if we can get a solution in js/ts. I have adapted a working c++ solution. It gets tests 1-6 correct, 7-9 wrong, everything else times out.
Code:
WTF i can do each query in O(n) time but i get time out on 3 questions, and stack overflow on 2 questions because the tree is too deep
this question is fuking RIDICULOUS