传送门：P3128 [USACO15DEC] Max Flow P
首先要学会差分qwq
题目意思：
给定一个节点数为 \(n\) 的树，有 \(m\) 次操作。
每次操作给你两个数 \(s\) 和 \(t\)，你需要在 \(s\) 到 \(t\) 的路径所经过点的运输压力 \(+1\)。
求最后运输压力最大的点的压力。
思路：
发现 \(s\) 到 \(t\) 的路径为 \(s\to lca(s,t)\to t\)
那么我们可以建立一个差分数组 \(cf\)
每次操作在 \(s\to lca(s,t)\) 和 \(t\to lca(s,t)\) 的路径经过的点上 +1，就是 \(cf_s+1\)，\(cf_t+1\)，\(cf_{lca(s,t)}-2\)
问题：
但是这样 lca(s,t) 相当于并没有 +1，为了解决这个问题，我们来看一张图：
现在所有的 \(cf\) 都是 \(0\)
此时我们想从 \(3\) 走到 \(1\)
很明显他们的 \(lca\) 为 \(4\)，按照上面的方法：我们能够得到：
这时开始遍历
void pressure(int now,int fa)
{
for(int i=fir[now];i;i=ed[i].next)
{
if(ed[i].v!=fa)
{
pressure(ed[i].v,now);
}
pres[now]+=pres[ed[i].v];
}
}
可以得到：
\(pres_1=1\)，\(pres_5=1\)，\(pres_3=1\)，\(pres_4=0\)，\(pres_2=0\)，\(pres_7=0\)，\(pres_6=0\)
观察到：pres_4 的值只会影响到他的父亲节点 6 的值，那么我们可以：
\(cf_4-1\)，\(cf_6-1\)
这样就能得出正确答案了喵~
最终思路：
每次询问求 s 和 t 的 lca，\(cf_s+=1\)，\(cf_t+=1\)，\(cf_{lca(s,t)}-=1\)，\(cf_{lca(s,t) 的 fa}-=1\)
最后遍历整棵树求最大值。