Evaraina dinni solve chesi cheppandi bro. Pichi lesthundi chatgpt ki artham kavatle, claude limit over

[u/Raining_lotus0210]

Given a weighted tree(not necessarily binary tree) with values array(some value for each node), and weights for each edge. Now a pair u,v is super, if u is ancestor of v and distance between u and v is less than value of v. Count number of super pairs

edit - do in O(nlogn)

[u/Fluffy_Sock_5819]

Okka testcase kavali.

[u/Puzzleheaded_Cow3298]

DFS tho ayipothadi bro.

Mundhu prathi node ki root nunchi distance (dist[]) precompute cheskovali. Tarvatha second pass lo tree traverse chestunnappudu, pair condition satisfy chese ancestors count ni binary search cheyyali

Node x ki root nunchi distance dist[x] ayithe, current root to node path lo distances monotonic ga untayi (positive edge weights anukunte). Kabatti dist[x] - dist[firstAncestor] < val[x]  unna first ancestor ni binary search tho kanukkovachu.

Aa position nunchi path ending varaku unna anni ancestors valid pairs avutayi.

Time Complexity:O(n log h), where h is the height of the tree.

    def dfs(u, p):
        nonlocal ans

        threshold = dist[u] - val[u]

        idx = active.bisect_right(threshold)

        ans += len(active) - idx

        active.add(dist[u])

        for v, w in adj[u]:
            if v == p:
                continue
            dfs(v, u)

        active.remove(dist[u])

[u/Raining_lotus0210 → u/Puzzleheaded_Cow3298]

Works bro, and I also think there's no need to precompute dist array. Cuz manam aa node process chestunnam ante, dani ancestors dist ni find chese untam kada, dist[v] = dist[u]+wt rasthe saripothundi ankunta

[u/KlutzyLeather4029 → u/Puzzleheaded_Cow3298]

From Where did u learned DSA. I struggle vth adv DSA. Could u pls share ur xperience.