python这是为什么

import sys
sys.setrecursionlimit(10**7)
input = lambda:sys.stdin.readline()
N = 100010
M = 200010
e = [0] * M
ne = [0] * M
h = [-1] * N
idx = 0
d = [0] * N

def add(a,b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    idx += 1

def check(x):
    # 只染k个紫色点,能否让最大的红色连通块大小<=x
    engry = k
    
    def dfs(u,fa):
        nonlocal x
        nonlocal engry
        if d[u] == 1 and fa != -1:
            return 1
        # 返回以u为根节点的子树的红色点个数
        c = 1
        i = h[u]
        while i!=-1:
            j = e[i]
            if j == fa:
                i = ne[i]
                continue
            c += dfs(j,u)
            i = ne[i]
        if c > x:
            engry -= 1
            c = 0
        return c
    
    dfs(1,-1)
    return engry >= 0

def binary(l,r):
    while l < r:
        mid = (l+r) >> 1
        if check(mid):
            r = mid
        else:
            l = mid + 1
    return l

n,k = map(int,input().split())

for i in range(n-1):
    a,b = map(int,input().split())
    add(a,b)
    add(b,a)
    d[a] += 1
    d[b] += 1

if n == k:
    print(0)
else:
#     for i in range(0,n+1):
#         print(check(i))
    ans = binary(1,n)
    print(ans)

全部评论
python的递归爆栈了,想解决这个问题,要么栈模拟DFS,要么搞个手写栈的模板
1 回复 分享
发布于 03-23 22:26 上海

相关推荐

04-29 00:12
小米_人力资源
牛客448863700号:也得看岗位呀,我还拿下美团呢,不说了送单了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务