[USACO15DEC] Max Flow P

题目描述

Farmer John has installed a new system of $N - 1$ pipes to transport milk between the $N$ stalls in his barn ( $2 \leq N \leq 50, 000$ ), conveniently numbered $1 \dots N$ . Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between $K$ pairs of stalls ( $1 \leq K \leq 100, 000$ ). For the $i$ th such pair, you are told two stalls $s_{i}$ and $t_{i}$ , endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from $s_{i}$ to $t_{i}$ , then it counts as being pumped through the endpoint stalls $s_{i}$ and

$t_{i}$ , as well as through every stall along the path between them.

FJ 给他的牛棚的 $N$ 个隔间之间安装了 $N - 1$ 根管道，隔间编号从 $1$ 到 $N$ 。所有隔间都被管道连通了。

FJ 有 $K$ 条运输牛奶的路线，第 $i$ 条路线从隔间 $s_{i}$ 运输到隔间 $t_{i}$ 。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

输入格式

The first line of the input contains $N$ and $K$ .

The next $N - 1$ lines each contain two integers $x$ and $y$ ( $x \neq = y$ ) describing a pipe

between stalls $x$ and $y$ .

The next $K$ lines each contain two integers $s$ and $t$ describing the endpoint

stalls of a path through which milk is being pumped.

第一行输入两个整数 $N$ 和 $K$ 。

接下来 $N - 1$ 行每行输入两个整数 $x$ 和 $y$ ，其中 $x \neq = y$ 。表示一根在牛棚 $x$ 和 $y$ 之间的管道。

接下来 $K$ 行每行两个整数 $s$ 和 $t$ ，描述一条从 $s$ 到 $t$ 的运输牛奶的路线。

输出格式

An integer specifying the maximum amount of milk pumped through any stall in the barn.

一个整数，表示压力最大的隔间的压力是多少。

样例 #1

样例输入 #1

样例输出 #1

提示

$2 \leq N \leq 5 \times 1 0^{4}, 1 \leq K \leq 1 0^{5}$

我的代码

N,K = tuple(map(int,input().split()))

g = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = tuple(map(int,input().split()))
    g[x].append(y)
    g[y].append(x)

import math
pows = int(math.ceil(math.log2(N)))
dep = [0 for _ in range(N+1)]
fa = [[0 for _ in range(pows+1)] for _ in range(N+1)]

def dfs(x:int,father:int):
    dep[x] = dep[father]+1
    fa[x][0] = father

    for i in range(1,pows+1):
        fa[x][i] = fa[fa[x][i-1]][i-1]
    
    for c in g[x]:
        if c!=father:
            dfs(c,x)

def lca(s:int,t:int)->int:
    if dep[s]<dep[t]:
        s,t = t,s
    
    for i in range(pows,-1,-1):
        if dep[fa[s][i]]>=dep[t]:
            s = fa[s][i]
    
    if s==t:
        return s

    for i in range(pows,-1,-1):
        if fa[s][i]!=fa[t][i]:
            s,t = fa[s][i],fa[t][i]
    
    return fa[s][0]

dfs(1,0)
diff = [0 for _ in range(N+1)]
for _ in range(K):
    s,t = tuple(map(int,input().split()))
    l = lca(s,t)
    diff[s] += 1
    diff[l] -= 1
    diff[t] += 1
    diff[fa[l][0]] -= 1

pressure = 0
def traverse(x:int,father:int)->int:
    global pressure
    res = 0
    for c in g[x]:
        if c!=father:
            res += traverse(c,x)
    res += diff[x]
    pressure = max(pressure,res)
    return res
traverse(1,0)
print(pressure)

思路我感觉是没啥问题的，差分数组维护链上点权，记得lca重复增量后（左支右支算两次）要减掉重复的，然后不要影响到lca父节点。
倍增LCA我交过板子，虽然T了也不是RE（洛谷所有语言评测时间和内存都一样，应该是py的问题不是代码的问题），我以为这题数组开小越界了，全改掉写死最大值也一样RE。然后差分以及回溯算后缀和这一块我注释掉再交一样RE，说明是LCA的问题？但是LCA这个直接打的板子啊，也看不出来哪有问题。

我洛谷不打比赛，没下载数据的次数，求各位佬解答，这个代码为啥会RE？