前言：
题目链接：P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
讲解：
这一题含金量真算高的，包含了建树（用了图论的知识），求最近公共祖先（倍增法），还有树上差分（第一次听树上还有差分吧）
这些知识有欠缺的去学习一下上面的几个小知识点吧
思路：
该题我一开始的思路是：虽然一个父亲有多个孩子，但是孩子只有一个父亲，就准备用一个fa数组或者一个map(孩子是键值)来存父子关系，然后有一个book数组，当输入s和t时，就从t加到s，用book标记每个点的经过次数，后面发现这个做法不可行----->原因1：给出的x和y并不确定哪个是父亲 原因2：s和t也不确定哪个是父亲------->思路转变
该题实际要（第四声）求的是：被经过最多次数的点；这个题涉及到的是图或者树，并且更改的是一段中的数据------->频繁更改某个区间------->想到差分----->树差分 （当涉及更改某个区间时，我想到了线段树，但是线段树一般方便查询的是 某个区间 的相关属性（如区间和），但是该题最后并未涉及和区间有关的求值，而是求单点的信息，因此线段树这种做法可以放后面考虑， 但是线段树是可以做的，也有相关的题解，感兴趣的和想复习线段树的大佬可以去做做）
AC代码：
代码语言：javascript复制const int N = 5e4 5;
const int M = N - 1;
int cnt;
int head[N];
int fa[N][21];
int deepth[N];
int power[N];
int ans;
struct EDGE
{
int v;
int next;
}EDGE[M * 2];
void add(int u, int v)
{
cnt ;
EDGE[cnt].v = v;
EDGE[cnt].next = head[u];
head[u] = cnt;
}
void dfs(int son, int father)
{
//第2^0个父亲就是这个父亲
fa[son][0] = father;
//儿子深度 = 父亲深度 1
deepth[son] = deepth[father] 1;
//算低2 ^ i个父亲是谁
for (int i = 1; (1 << i)/*注意不是i << 1*/ <= deepth[son]; i )
fa[son][i] = fa[fa[son][i - 1]][i -1];//公式
for (int i = head[son]; i; i = EDGE[i].next)
{
int v = EDGE[i].v;
if (v != father)/**/
dfs(v, son);
}
}
int lca(int x, int y)
{
if (deepth[x] < deepth[y])//要让x在y下面，这样子方便后面统一处理
swap(x, y);
//使得x,y位于同一高度
for (int i = 20; i >= 0; i--)//注意是逆序（原因:1、从上往下找比较快 2、若为顺序，则越往上走，找的父亲跨度越大，不符合要求）
{
if (deepth[fa[x][i]] >= deepth[y])
x = fa[x][i];
}
if (x == y)//如果两个点已经重合
return x;
//找公共祖先且使得x,y位于公共祖先的下一层
for (int i = 20; i >= 0; i--)
{
if (fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];//因为位于公共祖先的下一层，所以他们的父亲就是公共祖先
}
void getans(int son, int father)
{
for (int i = head[son]; i; i = EDGE[i].next)
{
if (EDGE[i].v == father)/**/
continue;
getans(EDGE[i].v, son);
power[son] = power[EDGE[i].v];
}
ans = max(ans, power[son]);
}
void solve()
{
int n, k;
cin >> n >> k;
int u, v, w;
//建树
for (int i = 0; i < n - 1; i )
{
cin >> u >> v;
add(u, v);
add(v, u);
}
dfs(1, 0);//求第2 ^ n个父亲
//求公共祖先、树上差分
for (int i = 0; i < k; i )
{
cin >> u >> v;
int togetherfather = lca(u, v);
power[u] ;
power[v] ;
power[togetherfather]--;
power[fa[togetherfather][0]]--;
}
getans(1, 0);
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
