题目大意：
给你一棵树，k 次操作，每次操作中有 a b 两点，这两点路上的所有点都被标记一次。问你 k 次操作之后，整棵树上的点中被标记的最大次数是多少。
分析：
1、由于数据太大，故可以采用树上差分中的点差分来做到 O（1）标记。
2、需要用 tarjan 离线找出两点间的 lca 。
3、在树上点差分中，还需要找到 lca 的父亲节点。由于在 tarjan 求 lca 时，并查集中的 pre[lca] 并非一直指向的是 lca 的父亲节点，故需要再开一个 fa[] 数组来标记出所有点的 父亲节点 （根节点可忽略）。
4、在求 lca 时，某点对可能被遍历超过一次，对差分的值有影响，故需要再用 flag[] 数组来标记当前点对是否是第一次被找到它们的 lca。
代码如下：
#include<iostream> #include<algorithm> #include<string.h> #define maxn 50008 using namespace std; int n,k,cnt,tot,ans; int head[maxn],qhead[maxn],e[maxn],fa[maxn],f[maxn]; bool vis[maxn],flag[200008]; struct Edge{ int to; int next; }edge[maxn<<1]; struct Query{ int to; int next; }s[200008]; inline void add(int u,int v){ edge[++cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt; return; } inline void qadd(int u,int v){ s[++tot].to=v; s[tot].next=qhead[u]; qhead[u]=tot; return; } inline int find(int x){ if(x==e[x]) return x; return e[x]=find(e[x]); } void tarjan(int u){ vis[u]=true; for(int i=head[u];i;i=edge[i].next){ int v=edge[i].to; if(vis[v]) continue; fa[v]=u; tarjan(v); e[v]=u; } for(int i=qhead[u];~i;i=s[i].next){ int v=s[i].to; if(vis[v]&&!flag[i]) { flag[i]=flag[i^1]=true; int lca=find(v); f[u]++,f[v]++; f[lca]--,f[fa[lca]]--; } } return; } void dfs(int u,int pre){ for(int i=head[u];i;i=edge[i].next){ int v=edge[i].to; if(v==pre) continue; dfs(v,u); f[u]+=f[v]; } ans=max(ans,f[u]); return; } int main() { scanf("%d%d",&n,&k); int A,B; for(int i=1;i<=n;i++) e[i]=i; for(int i=1;i<n;i++){ scanf("%d%d",&A,&B); add(A,B),add(B,A); } tot=-1; memset(qhead,-1,sizeof(qhead)); for(int i=1;i<=k;i++){ scanf("%d%d",&A,&B); qadd(A,B),qadd(B,A); } tarjan(1); dfs(1,-1); printf("%d\n",ans); }
洛谷P3128 [USACO15DEC]最大流Max Flow （树上差分）
原文：https://www.cnblogs.com/Absofuckinglutely/p/11945904.html