Description

FJ给他的牛棚的(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间运输到隔间。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。（洛谷翻译）

Solution

简单的树上差分，对于树上一条链上所有节点加1的操作，用 表示节点 的第 个祖先， 表示 的最近公共祖先，可以转化成




统计答案的时候只需要 统计子树的值之和即可
例如下图：

对(1, 3)所在的链进行差分，在 的时候得到的结果是
符合我们的预期结果。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
bool vis[50005];
int dep[50005], fa[50005][32], sum[50005], ans;
vector<int> G[50005];
void bfs(int root) {
  queue<int> q;
  q.push(root);
  fa[root][0] = 0;
  dep[root] = 0;
  vis[root] = true;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = 1; i <= 20; i++) {
      fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (auto &it : G[u]) {
      if (!vis[it]) {
        q.push(it);
        vis[it] = true;
        dep[it] = dep[u] + 1;
        fa[it][0] = u;
      }
    }
  }
}
int LCA(int u, int v) {
  if (dep[u] > dep[v]) swap(u, v);
  int hu = dep[u], hv = dep[v];
  int tu = u, tv = v;
  for (int det = hv - hu, i = 0; det; det >>= 1, i++) {
    if (det & 1) {
      tv = fa[tv][i];
    }
  }
  if (tu == tv) return tu;
  for (int i = 20; i >= 0; i--) {
    if (fa[tu][i] == fa[tv][i]) continue;
    tu = fa[tu][i];
    tv = fa[tv][i];
  }
  return fa[tu][0];
}
void dfs(int u, int par) {
  for (auto &it : G[u]) {
    if (it == par) continue;
    dfs(it, u);
    sum[u] += sum[it];
  }
  ans = max(ans, sum[u]);
}
void solve() {
  int n, m; cin >> n >> m;
  for (int i = 1; i <= n - 1; i++) {
    int u, v; cin >> u >> v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  bfs(1);
  while (m--) {
    int u, v; cin >> u >> v;
    int lca = LCA(u, v);
    sum[u]++, sum[v]++, sum[lca]--, sum[fa[lca][0]]--; //树上差分
  }
  dfs(1, 0);
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int T = 1; //cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}