树上差分学习笔记 + [USACO15DEC]最大流$Max \ \ Flow \ \ By$

时间：2023-03-10 07:13:38
树上差分学习笔记 + [USACO15DEC]最大流$Max \ \ Flow \ \ By$

#\(\mathcal{\color{red}{Description}}\)

\(Link\)

\(FJ\)给他的牛棚的\(N(2≤N≤50,000)\)个隔间之间安装了\(N-1\)根管道，隔间编号从\(1\)到\(N\)。所有隔间都被管道连通了。

\(FJ\)有\(K(1≤K≤100,000)\)条运输牛奶的路线，第i条路线从隔间\(s_i\)运输到隔间\(t_i\)。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

#\(\color{red}{\mathcal{Solution}}\)

好的，今天学习了树上差分，感觉海星\(qwq\)。

树上差分

差分主要用来解决区间加减、单点查询一类问题，。那么所谓树上差分……顾名思义就是在树上搞差分，而在树上的操作就要丰富得多，可以支持链上修改、单点查询。很显然的是，树上差分遵循的原则应该是儿子加父亲减，从而达到逻辑关系一定的目的。而事实上一共有两种差分方式：

·边差分

边差分适用于更改边权对于普通的边差分而言，我们不妨把每条边的标记打在深度较大的点上因为并不可以打在深度小的点上，然后很显然的为了防止标记“蔓延”，所以我们要$$dif_u ++,dif_v++,dif_{LCA(u,v)} -= 2$$

·点差分

所谓点差分，就是指给定一段树上的链，执行修改操作。此时需要的是$$dif_u--,dif_v--,dif_{LCA(u,v)} --,dif_{father(LCA(u,v)}--$$跟边差分不同的是，我们现在每个点的\(dif\)是为了点服务的，所以我们的\(LCA\)也应当算上，那么就不能 \(-= 2\)，而是转而对\(father(LCA)\)进行操作。

那么最后就是标准的\(dfs\)统计了，随便乱搞就行。

#include <cmath>

#include <cstdio>

#include <iostream>

#define MAXN 200010

using namespace std ;

struct edge{

    int to, next ;

}e[MAXN << 1]; int head[MAXN], cnt ;

int N, M, A, B, C, i, j, Up, pre, res ;

int dif[MAXN], fa[MAXN][32], dep[MAXN], ans[MAXN] ;

inline int qr(){

    int k = 0 ; char c = getchar() ;

    while(!isdigit(c)) c = getchar() ;

    while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ;

    return k ;

}

inline void add(int u, int v){

    e[++ cnt].to = v ;

    e[cnt].next = head[u] ;

    head[u] = cnt ;

}

void _build(int deep, int now, int f){

    fa[now][0] = f ; dep[now] = deep ;

    for(int k = head[now]; k ;k = e[k].next){

        if(e[k].to == f) continue ;

        _build(deep + 1, e[k].to, now) ;

    }

}

void _get(int now){

    for(int k = head[now]; k ; k = e[k].next){

        if(e[k].to == fa[now][0]) continue ;

        _get(e[k].to) ;

        dif[now] += dif[e[k].to] ;

    }

    res = max(res, dif[now]) ;

}

inline void init(){

    Up = log(N) / log(2) + 1 ;

    for(i = 1; i <= Up; i ++)

        for(j = 1; j <= N; j ++)

            fa[j][i] = fa[fa[j][i - 1]][i - 1] ;

}

inline int LCA(int u, int v){

    if(dep[u] < dep[v]) swap(u, v) ;

    pre = dep[u] - dep[v] ;

    for(j = 0; j <= Up; j ++) if((1 << j) & pre) u = fa[u][j] ;

    if(u == v) return u ;

    for(j = Up; j >= 0; j --) if(fa[u][j] != fa[v][j]) u = fa[u][j], v = fa[v][j] ;

    return fa[v][0] ;

}

int main(){

    cin >> N >> M ;

    for(i = 1; i < N; i ++) A = qr(), B = qr(), add(A, B), add(B, A) ;

    _build(1, 1, 0) ; init() ;

    for(i = 1; i <= M; i ++){

        A = qr(), B = qr(), C = LCA(A, B);

        dif[A] ++, dif[B] ++ ;

        dif[C] --, dif[fa[C][0]] -- ;

    }

    _get(1) ; cout << res ;	return 0 ;

}

相关文章