树上差分

典型树上差分例题

前缀和差分讲解

tarjon_lca

例题：
Max Flow P

个人感悟：

1. tarjon

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

2. 树上差分和树上前缀

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

//https://www.luogu.com.cn/problem/P3128
//树上点差分的典型例题
//虽然K的值很大，但N的值也不小，所以这里采用tarjon的做法，如果无法通过
//更换为倍增的方法进行对比
#include
#define LOCAL
using namespace std;
const int maxn=5e4+10;
const int maxk=1e5+10;
vector link[maxn];
vector 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;ians) ans=psr[frt];
}

int main(){
    #ifdef LOCAL
    freopen("input.txt","r",stdin);
    #endif
    int N=read(),K=read();
    for (int i=0;i