典型树上差分例题

前缀和差分讲解

tarjon_lca

例题：
Max Flow P

个人感悟：

1. tarjon

感觉tarjon算法巧妙的利用了数据结构--并查集，将直观的寻找lca 的思想方法实习出来，在实现tarjon算法的过程中我对dfs的理解又加深了，dfs“去”和“回”的代码空间可以实现不同的功能顺序；

2. 树上差分和树上前缀

首先，树上前缀必须从下往上，因为从上往下会导致枝蔓变化，从下往上是单一路径。因此树上差分从下往上过程中是：父节点存储原父节点值减去所有原子节点值。

//https://www.luogu.com.cn/problem/P3128
//树上点差分的典型例题
//虽然K的值很大，但N的值也不小，所以这里采用tarjon的做法，如果无法通过
//更换为倍增的方法进行对比
#include<bits/stdc++.h>
#define LOCAL
using namespace std;
const int maxn=5e4+10;
const int maxk=1e5+10;
vector<int> link[maxn];
vector<int> path[maxn];
int psr[maxn];  //presure-->psr
int vis[maxn];
int parent[maxn];
int fa[maxn];
int ans=0;
//read改良版
int read(){
    int s=0,f=1,c=getchar();
    while(c<'0' || c>'9') { if (c=='-') f=-1;c=getchar();}
    // while(c>='0' && c<='9') {s=s*10+c-'0';c=getchar();}
    while (c>='0' && c<='9') { s=(s<<3)+(s<<1)+c-'0'; c=getchar();}
    return f*s;
}
// union_find_set
int find(int p){
    return fa[p]=(fa[p]==p)?p:find(fa[p]);
}

// 不得不说，tarjon算法最令我惊喜的是并查集和fa[]数组的使用与dfs的结合（好吧，把tarjon直接说出来了）
// 这其中的细节其实是利用dfs很好的思想，让dfs的功能体现的很好！
void dfs_tarjon(int p,int frt){
    parent[p]=frt;
    int len=(int)link[p].size();
    for (int i=0;i<len;++i){
        if (link[p][i]==frt) continue;
        dfs_tarjon(link[p][i],p);
    }
    // tmproot=frt;
    vis[p]=1;
    int len2=(int)path[p].size();
    // if (p==5) cout<<len2<<endl;
    for (int i=0;i<len2;++i){
        if (vis[path[p][i]]){
            int lca=find(path[p][i]);
            // cout<<p<<" and "<<path[p][i]<<" lca :"<<lca<<endl;
            // do something (就在这干事吧，毕竟我也不想再将lca对应的存起来了，太占用资源且麻烦了
            // 树的前缀和必须自下而上
            psr[p]+=1;
            psr[path[p][i]]+=1;
            psr[lca]-=1;
            psr[parent[lca]]-=1;
        }
    }
    fa[p]=frt;
}

void dfs_prefix(int p,int frt){
    int len=(int) link[p].size();
    for (int i=0;i<len;++i){
        if (link[p][i]==frt) continue;
        dfs_prefix(link[p][i],p);
    }
    psr[frt]+=psr[p];
    if (psr[frt]>ans) ans=psr[frt];
}

int main(){
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    int N=read(),K=read();
    for (int i=0;i<N-1;++i) {
        int u=read(),v=read();
        link[u].push_back(v);
        link[v].push_back(u);
    }
    for (int i=0;i<K;++i){
        int s=read();
        int t=read();
        path[s].push_back(t);
        path[t].push_back(s);
    }
    // init 并查集
    for (int i=1;i<=N;++i) fa[i]=i;
    dfs_tarjon(1,0);
    dfs_prefix(1,0);
    printf("%d",ans);
    return 0;
}