【树上点差分、LCA】Max Flow P
核心思路
[USACO15DEC] Max Flow P - 洛谷
sum[u]++,sum[v]++,sum[lca(u,v)]--,sum[fa[lca(u,v)]];
本质上就是，对树进行差分
自底向上进行统计处理
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 200000+10;
vector<int> G[N] ;
int dep[N],fa[N],hson[N],sz[N],top[N],dfn[N],res[N];
//____________________________________分割线。
void dfs1(int u,int p){//u当前访问到的，p父节点。fa[u] = p;sz[u] = 1;dep[u] = dep[p]+1;hson[u] = -1;for(int i = 0;i < G[u].size();i++){int v = G[u][i];if(v == p)continue;dfs1(v,u);sz[u]+=sz[v];if(hson[u] == -1|| sz[v] > sz[hson[u]]){hson[u] = v;}} }
int cnt;//记录是第几次访问
void dfs2(int u,int p){if(u == 1)top[1] = 1;//先遍历重儿子 cnt++;dfn[u] = cnt; res[cnt] = u;if(hson[u] == -1)return;top[hson[u]] = top[u];dfs2(hson[u],u); for(int i = 0;i < G[u].size();i++){int v = G[u][i];if(v == p || hson[u] == v)continue;top[v] = v;dfs2(v,u);}
}
int lca(int u,int v){if(top[u] == top[v])return dep[u]<dep[v] ? u : v;//那个深度小就取哪个。if(dep[top[u]]<dep[top[v]]) return lca(u,fa[top[v]]);else return lca(fa[top[u]],v);//因为他是要跳到top的父亲上所以要比较两个top的深度；
}
int sum[114514];
int ans = 0;
void ges(int u,int f){for(int v:G[u]){if(v == f)continue;ges(v,u);sum[u]+=sum[v];}ans = max(sum[u],ans);
}
int main(){cin>>n>>m;for(int i = 1;i <= n-1;i++){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);} dfs1(1,0);dfs2(1,0);while(m--){int u,v;cin>>u>>v;int L = lca(u,v);sum[u]++,sum[v]++;sum[L]--,sum[fa[L]]--;}ges(1,0);cout<<ans<<endl;return 0;
}