思路1（树上倍增$ + $树上差分）
每次都修改一条从\(u\)到\(v\)，不就是树上差分的专门操作吗？？
直接用倍增求\(LCA\)，每次\(d[u]++,d[v]++,d[LCA(u,v)]--,d[f[LCA(u,v)][0]]--\)。
最后记得算下前缀和。
代码1
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010,M = 2 * N,MAX_LOG = 20;
int n,m;
int h[N],e[M],ne[M],idx;
int w[N];
int dep[N];
int f[N][MAX_LOG];
void add (int a,int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs1 (int u,int fa) {
f[u][0] = fa;
for (int i = 1;i <= MAX_LOG - 1;i++) f[u][i] = f[f[u][i - 1]][i - 1];
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dep[j] = dep[u] + 1;
dfs1 (j,u);
}
}
int get_LCA (int a,int b) {
if (dep[a] < dep[b]) swap (a,b);
for (int i = MAX_LOG - 1;i >= 0;i--) {
if (dep[f[a][i]] >= dep[b]) a = f[a][i];
}
if (a == b) return a;
for (int i = MAX_LOG - 1;i >= 0;i--) {
if (f[a][i] != f[b][i]) a = f[a][i],b = f[b][i];
}
return f[a][0];
}
int dfs2 (int u,int fa) {
int ans = 0;
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == fa) continue;
ans = max (ans,dfs2 (j,u));
w[u] += w[j];
}
return max (ans,w[u]);
}
int main () {
memset (h,-1,sizeof (h));
cin >> n >> m;
for (int i = 1;i <= n - 1;i++) {
int a,b;
cin >> a >> b;
add (a,b),add (b,a);
}
dfs1 (1,0);
while (m--) {
int a,b;
cin >> a >> b;
int anc = get_LCA (a,b);
w[a]++,w[b]++,w[anc]--,w[f[anc][0]]--;
}
cout << dfs2 (1,0) << endl;
return 0;
}
思路2（树链剖分）
修改一条\(u\)到\(v\)的路径，查询整棵树的最大值，不就是树剖的模板吗？？
直接套模板（懒得讲
代码2
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010,M = 2 * N,MAX_LOG = 20;
int n,m;
int h[N],e[M],ne[M],idx;
int timestamp;
int dep[N],s[N],son[N],fa[N];
int id[N],top[N];
struct segment_tree_node {
int l,r;
int maxx,add;
}tr[4 * N];
void add (int a,int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void push_up (int u) {
tr[u].maxx = max (tr[u << 1].maxx,tr[u << 1 | 1].maxx);
}
void push_down (int u) {
auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];
if (root.add) {
left.maxx += root.add,left.add += root.add;
right.maxx += root.add,right.add += root.add;
root.add = 0;
}
}
void build_segment_tree (int u,int l,int r) {
if (l == r) {
tr[u] = {l,r,0,0};
return ;
}
tr[u] = {l,r};
int mid = l + r >> 1;
build_segment_tree (u << 1,l,mid),build_segment_tree (u << 1 | 1,mid + 1,r);
push_up (u);
}
void modify (int u,int l,int r,int d) {
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].add += d,tr[u].maxx += d;
return ;
}
push_down (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify (u << 1,l,r,d);
if (r >= mid + 1) modify (u << 1 | 1,l,r,d);
push_up (u);
}
int query_max (int u,int l,int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].maxx;
push_down (u);
int mid = l + r >> 1;
int ans = 0;
if (l <= mid) ans = max (ans,query_max (u << 1,l,r));
if (r >= mid + 1) ans = max (ans,query_max (u << 1 | 1,l,r));
return ans;
}
void dfs1 (int u,int f) {
dep[u] = dep[f] + 1,s[u] = 1,fa[u] = f;
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == f) continue;
dfs1 (j,u);
s[u] += s[j];
if (s[j] > s[son[u]]) son[u] = j;
}
}
void dfs2 (int u,int top_node) {
id[u] = ++timestamp,top[u] = top_node;
if (!son[u]) return ;
dfs2 (son[u],top_node);
for (int i = h[u];~i;i = ne[i]) {
int j = e[i];
if (j == fa[u] || j == son[u]) continue;
dfs2 (j,j);
}
}
void modify_path (int a,int b) {
while (top[a] != top[b]) {
if (dep[top[a]] < dep[top[b]]) swap (a,b);
modify (1,id[top[a]],id[a],1);
a = fa[top[a]];
}
if (dep[a] > dep[b]) swap (a,b);
modify (1,id[a],id[b],1);
}
int query_subtree (int u) {
return query_max (1,id[u],id[u] + s[u] - 1);
}
int main () {
memset (h,-1,sizeof (h));
cin >> n >> m;
for (int i = 1;i <= n - 1;i++) {
int a,b;
cin >> a >> b;
add (a,b),add (b,a);
}
build_segment_tree (1,1,n),dfs1 (1,0),dfs2 (1,1);
while (m--) {
int a,b;
cin >> a >> b;
modify_path (a,b);
}
cout << query_subtree (1) << endl;
return 0;
}