bzoj4390

树上差分

感觉挺巧妙的。。。

每次更新就是在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 ;

}