题号 NC24019
名称 Max Flow
来源 USACO英文版-2015 December Contest-Platinum
每日一题三期汇总贴~


如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：jzdx（hjh）

算法1

(最近公共祖先 + 树上差分)

如果是一维数组求每个点被区间覆盖的次数我们可以用差分

问题转化到了树上同样可以用差分

树上差分

1. 用数组维护每个点被路径覆盖的次数

2. 设存在一条路径，我们令

   

3. 用将从叶节点累加起来

4. 最后数组就是每个点被路径覆盖的次数

画图更直观一些

1. 令

   

   图中的数值表示数组中的值

2. 进行

   

3. 结果

   

在进行的过程中用全局变量维护最大值

我使用的是倍增求时间复杂度为

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
//#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
const int N = 50010,M = N * 2;
int h[N],ne[M],e[M],idx;
int d[N];
int fa[17][N],dep[N];
int ans;
int n,m;

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs1(int u,int father)
{
    fa[0][u] = father;
    dep[u] = dep[father] + 1;
    for(int k = 1;k <= 16;k ++)
        fa[k][u] = fa[k - 1][fa[k - 1][u]];
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs1(j,u);
    }
}

void dfs2(int u,int father)
{
    for(int i =h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs2(j,u);
        d[u] += d[j];
    }
    ans = max(ans,d[u]);
}

int lca(int a,int b)
{
    if(dep[a] < dep[b]) swap(a,b);
    for(int k = 16;k >= 0;k --)
        if(dep[fa[k][a]] >= dep[b])
            a = fa[k][a];
    if(a == b) return a;
    for(int k = 16;k >= 0;k --)
        if(fa[k][a] != fa[k][b])
        {
            a = fa[k][a];
            b = fa[k][b];
        }
    return fa[0][a];
}


void solve()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i = 1;i < n;i ++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs1(1,0);
    while(m --)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int anc = lca(a,b);
        d[a] ++,d[b] ++,d[anc] --,d[fa[0][anc]] --;
    }
    dfs2(1,0);
    printf("%d\n",ans);
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL
    int T = 1;
    // init(N - 1);
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目4月21日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴