题号 NC24019
名称 Max Flow
来源 USACO英文版-2015 December Contest-Platinum

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给你一棵树个节点的树，再给你条树上的简单路径，问树上的点被路径覆盖最多的次数是多少

样例

输入
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
输出
9

算法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;
}