前言：
題目鏈接：P3128 [USACO15DEC] Max Flow P - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
講解：
這一題含金量真算高的，包含了建樹（用了圖論的知識），求最近公共祖先（倍增法），還有樹上差分（第一次聽樹上還有差分吧）
這些知識有欠缺的去學習一下上面的幾個小知識點吧
?思路：
該題我一開始的思路是：雖然一個父親有多個孩子，但是孩子只有一個父親，就準備用一個fa數組或者一個map(孩子是鍵值)來存父子關系，然后有一個book數組，當輸入s和t時，就從t加到s，用book標記每個點的經過次數，后面發現這個做法不可行----->原因1：給出的x和y并不確定哪個是父親? ? ? ? 原因2：s和t也不確定哪個是父親------->思路轉變
該題實際要（第四聲）求的是：被經過最多次數的點；這個題涉及到的是圖或者樹，并且更改的是一段中的數據------->頻繁更改某個區間------->想到差分----->樹差分
（當涉及更改某個區間時，我想到了線段樹，但是線段樹一般方便查詢的是?某個區間???的相關屬性（如區間和），但是該題最后并未涉及和區間有關的求值，而是求單點的信息，因此線段樹這種做法可以放后面考慮， 但是線段樹是可以做的，也有相關的題解，感興趣的和想復習線段樹的大佬可以去做做）
AC代碼：
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;//兒子深度 = 父親深度 + 1deepth[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;
}
