树上差分
感觉挺巧妙的。。。
每次更新就是在u,v上+1,x是lca(u,v),在x和fa[x]上-1,那么每个点的权值就是子树和,正确性yy一下就行了
不过树状数组的常数真是小,改成前缀和才快了200ms
#include<bits/stdc++.h>
using namespace std;
const int N = ;
int n, m, ans, cnt = , dfs_clock;
int head[N], fa[N][], in[N], out[N], dep[N], sum[N];
struct edge {
int nxt, to;
} e[N << ];
void link(int u, int v)
{
e[++cnt].nxt = head[u];
head[u] = cnt;
e[cnt].to = v;
}
int lca(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int i = ; i >= ; --i) if(d & ( << i)) u = fa[u][i];
if(u == v) return u;
for(int i = ; i >= ; --i) if(fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
return fa[u][];
}
void dfs(int u, int last)
{
in[u] = ++dfs_clock;
for(int i = head[u]; i; i = e[i].nxt) if(e[i].to != last)
{
fa[e[i].to][] = u;
dep[e[i].to] = dep[u] + ;
dfs(e[i].to, u);
}
out[u] = dfs_clock;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i < n; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
link(u, v);
link(v, u);
}
dfs(, );
for(int j = ; j <= ; ++j)
for(int i = ; i <= n; ++i)
fa[i][j] = fa[fa[i][j - ]][j - ];
while(m--)
{
int u, v, x;
scanf("%d%d", &u, &v);
x = lca(u, v);
++sum[in[u]];
++sum[in[v]];
--sum[in[x]];
--sum[in[fa[x][]]];
}
for(int i = ; i <= n; ++i) sum[i] += sum[i - ];
for(int i = ; i <= n; ++i) ans = max(ans, sum[out[i]] - sum[in[i] - ]);
printf("%d\n", ans);
return ;
}