val 存储的是 U 到父亲节点的权值

点差分

lca = LCA(u,v);
val[u]+=x , val[v]+=x , val[lca]-=x , val[far[lca]] -=x ;

边差分

lca = LCA(u,v);
val[u]+=x , val[v]+=x , val[lca]-=2*x ;

Network 【边差分】

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
const int mxn = 4e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 199999 ;
using namespace std;
#define open freopen("input.in","r",stdin);freopen("output.in","w",stdout);
typedef long long ll;
template <class T>
void rd(T &x){
    x=0;T f=1;char c=getchar();
    while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
    while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
    x*=f;
}
int p,t,n,m,k,si,res,cnt,lg,ans;
int to[mxn] , head[mxn] , nx[mxn] ,in[mxn] ,pre[mxn] , val[mxn] ,dep[mxn];
int f[mxn][30];
void add(int u,int v){to[cnt]=v; nx[cnt]=head[u]; head[u]=cnt++;}
void DFS(int u,int pre)
{
    dep[u] = dep[pre]+1 ; f[u][0] = pre ;
    for(int i=1;i<=lg;i++){
        f[u][i] = f[ f[u][i-1] ][i-1];
    }
    for(int i=head[u];~i;i=nx[i]){
        int v = to[i] ;
        if(v!=pre) DFS(v,u);
    }
}
int LCA(int u,int v)
{
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=lg;i>=0;i--){
        if(dep[f[v][i]]>=dep[u])
            v = f[v][i];
    }
    if(u==v) return u;
    for(int i=lg;i>=0;i--){
        if(f[u][i]!=f[v][i])
            u = f[u][i] , v = f[v][i] ;
    }
    return f[u][0];
}
void up(int u,int v){val[u]++; val[v]++;val[LCA(u,v)]-=2;}
void query(int u,int pre)
{
    for(int i=head[u];~i;i=nx[i]){
        int v = to[i] ;
        if(v==pre) continue;
        query(v,u);
        val[u]+=val[v];
        if(!val[v]) ans+=m;
        else if(val[v]==1) ans++;
    }
}
void init()
{
    cnt = 0 ;  ans = 0 ;
    lg = log2((double)n)+1;
    memset(head,-1,sizeof(head));
    memset(dep,0,sizeof(dep));
}
void solve()
{
    rd(n) , rd(m) ; init() ;
    for(int i=1,u,v;i<n;i++){
        rd(u) , rd(v) ;
        add(u,v) ; add(v,u) ;
    }
    DFS(1,0);
    for(int i=1,u,v;i<=m;i++){
        rd(u) , rd(v) ; up(u,v) ;
    }
    query(1,0);
    printf("%d\n", ans );
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
}

P3128 [USACO15DEC]Max Flow P 【点差分】

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#define pi acos(-1.0)
#define eps 1e-9
const int mxn = 4e5+7 ;
const int INF = 0x3f3f3f3f ;
const int mod = 199999 ;
using namespace std;
#define open freopen("input.in","r",stdin);freopen("output.in","w",stdout);
typedef long long ll;
template <class T>
void rd(T &x){
    x=0;T f=1;char c=getchar();
    while(!isdigit(c)) {if(c=='-') f = -1 ; c = getchar();}
    while(isdigit(c)) {x = (x<<1) + (x<<3) + (c^48);c = getchar();}
    x*=f;
}
int p,t,n,m,k,si,res,cnt,lg,ans;
int to[mxn] , head[mxn] , nx[mxn] ,in[mxn] ,pre[mxn] , val[mxn] ,dep[mxn];
int f[mxn][30];
void add(int u,int v){to[cnt]=v; nx[cnt]=head[u]; head[u]=cnt++;}
void DFS(int u,int pre)
{
    dep[u] = dep[pre]+1 ; f[u][0] = pre ;
    for(int i=1;i<=lg;i++){
        f[u][i] = f[ f[u][i-1] ][i-1];
    }
    for(int i=head[u];~i;i=nx[i]){
        int v = to[i] ;
        if(v!=pre) DFS(v,u);
    }
}
int LCA(int u,int v)
{
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=lg;i>=0;i--){
        if(dep[f[v][i]]>=dep[u])
            v = f[v][i];
    }
    if(u==v) return u;
    for(int i=lg;i>=0;i--){
        if(f[u][i]!=f[v][i])
            u = f[u][i] , v = f[v][i] ;
    }
    return f[u][0];
}
void up(int u,int v)
{
    int lca = LCA(u,v) ;
    val[u]++; 
    val[v]++;
    val[lca]--;
    val[f[lca][0]]--;
}
void query(int u,int pre)
{
    for(int i=head[u];~i;i=nx[i]){
        int v = to[i] ;
        if(v==pre) continue;
        query(v,u);
        val[u]+=val[v];
    }
    ans = max(ans,val[u]);
}
void init()
{
    cnt = 0 ;  ans = 0 ;
    lg = log2((double)n)+1;
    memset(head,-1,sizeof(head));
    memset(dep,0,sizeof(dep));
}
void solve()
{
    rd(n) , rd(m) ; init() ;
    for(int i=1,u,v;i<n;i++){
        rd(u) , rd(v) ;
        add(u,v) ; add(v,u) ;
    }
    DFS(1,0);
    for(int i=1,u,v;i<=m;i++){
        rd(u) , rd(v) ; up(u,v) ;
    }
    query(1,0);
    printf("%d\n", ans );
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
}