Description
Problem:https://www.luogu.com.cn/problem/P3128
FJ 给他的牛棚的 \(N\) 个隔间之间安装了 \(N-1\) 根管道，隔间编号从 \(1\) 到 \(N\)。所有隔间都被管道连通了。
FJ 有 \(K\) 条运输牛奶的路线，第 \(i\) 条路线从隔间 \(s_i\) 运输到隔间 \(t_i\)。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。
Analysis
前置知识：LCA
本题是树上差分的模板题，借本题我们来讲解一下树上差分。
注意到没有修改操作，每条路径 \(u-v\) 都给路径 \(u-v\) 上的每个点压力 +1，考虑树上差分。
树上差分和线性差分不是很相同，线性差分对于区间 \(a\{l,r\}\) 的每个值加 \(x\),我们只需要 \(a_r+x,a_{l-1}-x\) 即可。
回忆一下线性差分的本质，它的本质是 将区间 \(\{1,r\}\) 的每一个值 \(+x\)，再将区间 \(\{1,l-1\}\) 的每一个值都 \(-x\)，消除多余的影响。
对于树上差分，记 \(LCA(u,v)\) 表示 \(u,v\) 的最近公共祖先，则路径 \(u-v\) 为：\(u-LCA(u,v)-v\)
点差分和边差分还是不同的，这里先讲解本题的点差分。
为了解释方便，这里假设 \(root = 1\)。
首先将点集 \(\{1,u\}\) 上的每一个点的贡献 \(+x\)，再将点集 \(\{1,v\}\) 上的每一个点 \(+x\)，显然有多余的贡献。注意到 \(LCA(u,v)\) 也属于路径上的点，它只需要一次贡献，但是我们对它进行了两次计算，所以从 root到 \(LCA(u,v)\) 的贡献 \(-x\)。
其余的从 \(1\) 到 \(fa_{LCA(u,v)}\) 的点本应没有贡献，但是我们计算了两次贡献，在处理 \(LCA(u,v)\) 的时候已经消除了一次贡献，我们再对它消除一次贡献即可。也就是令 \(fa_{LCA(u,v)} - x\)。
这是对于本题的点差分而言，对于边差分，由于我们不需要考虑 \(LCA(u,v)\) 的贡献，所以我们在分别处理从 1 到 \(u,v\) 的贡献后再将从1到 \(LCA(u,v)\) 的贡献减去即可。
差分数组完成后，最后 dfs 累加即可。也就是树上前缀和操作。
这里给出一颗树供理解：
假设我们要求 \(6\) 号点到 \(9\) 号点上的路径，对于点差分，将 \(power_6 ++\) 也就是将从 root 到 \(6\) 号点的贡献标记为 + 1，同理对于 \(power_9 ++\) 。对于重复的贡献，\(LCA(6,9)\) 多计算了一次贡献，\(power_3--\)，同时，从 root 到 \(3\) 的父节点也就是 2 及以上的点都被多统计了两次贡献，需要 --；
对于边差分，对于重复性的答案我们只需要将 \(LCA(u,v)\) 的贡献减去两次多余的贡献即可。这样就会确保我们的标记不会向 \(LCA\) 及以上延伸。
这就是树上差分的基本思想，总体来说，树上差分包括点差分和边差分，两者的处理方式有所不同。
计算 LCA 的时候为方便，倍增足够。
参考模板代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
int n,m,s;
vector <int> Edge[N];
int fa[N][100];
int depth[N*2];
int power[N];
int ans = 0;
void dfs(int noww,int fat)
{
// cout<<noww<<endl;
fa[noww][0] = fat;
depth[noww] = depth[fat] + 1;
for(int i=1;(1<<i) <= depth[noww];i++)
{
fa[noww][i] = fa[fa[noww][i-1]][i-1]; //递推求解
}
for(int i=0;i<Edge[noww].size();i++)
{
int v = Edge[noww][i];
if(v != fat)
{
dfs(v,noww);
}
}
}
int lca(int a,int b)
{
if(depth[a] > depth[b]) swap(a,b);
for(int i=20;i>=0;i--)
{
if(depth[a] <= depth[b]-(1<<i)) b = fa[b][i];
}
if(a == b) return a;
for(int i=20;i>=0;i--)
{
if(fa[a][i] == fa[b][i]) continue;
a = fa[a][i];
b = fa[b][i];
}
return fa[a][0];
}
void get(int u,int fat)
{
for(int i=0;i<Edge[u].size();i++)
{
int v = Edge[u][i];
if(v == fat) continue;
get(v,u);
power[u] += power[v];
}
ans = max(ans,power[u]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
Edge[x].push_back(y);
Edge[y].push_back(x);
}
dfs(1,0);
while(m--)
{
int a,b;
cin>>a>>b;
int LCA = lca(a,b);
++ power[a];
++ power[b];
-- power[LCA];
-- power[fa[LCA][0]];
}
get(1,0);
cout<<ans<<endl;
return 0;
}