差分 get ！

A4paper · 2018-09-23 11:17:54 · 个人记录

差分：

类似于前缀和，

不过前缀和的维护是从 L 跑到 R ，所以是 O ( n ) 的

差分只需要 num [ L ] + 1 ，num [ R + 1 ] - 1，然后在输出答案时再跑前缀和就行了

这样对于每次操作就是 O ( 1 ) 的了

树上差分：

如果一棵树退化成了一条链，那么就是普通的差分了，既然是一棵树，那么每次就要维护 x 到 y 的路径上的值，

所以利用差分的话就是 num [ x ] + 1，num [ y ] + 1，因为此时 LCA 被加了两次，所以 - 1，根据差分，fa [ LCA ] 也要 - 1

模板：

传送门

求 LCA 的话我用的树剖。

#define Max(a,b) dep[a]<dep[b] ? a : b

void dfs1(int u, int fa)
{
    FA[u] = fa;
    size[u] = 1;
    dep[u] = dep[fa]+1;
    for(int k=head[u];k;k=map[k].next)
    {
        int v = map[k].to;
        if(v == fa) continue;
        dfs1(v,u);
        size[u] += size[v];
        if(size[v] > size[son[u]])  son[u] = v;
    }
}
void dfs2(int u, int top)
{
    Top[u] = top;
    if(!son[u]) return;
    dfs2(son[u],top);
    for(int k=head[u];k;k=map[k].next)
    {
        int v = map[k].to;
        if(v==FA[u] || v==son[u])   continue;
        dfs2(v,v);
    }
}

int LCA(int x, int y)
{
    int nx = Top[x];
    int ny = Top[y];
    while(nx != ny)
    {
        if(dep[nx] < dep[ny])
        {
            swap(nx,ny);
            swap( x, y);
        }
        x = FA[nx];
        nx = Top[x];
    }
    if(x == y)  return x;
    return Max(x,y);
}

void check(int u)
{
    for(int k=head[u];k;k=map[k].next)
    {
        int v = map[k].to;
        if(v == FA[u])  continue;
        if(size[v] != 1)    check(v);
        num[u] += num[v];
        ans = max(ans,num[u]);
    }
}

int main(void)
{
    cin >> n >> k;
    for(int i=1,u,v;i<n;i++)
    {
        cin >> u >> v;
        add(u,v);   add(v,u);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1,u,v;i<=k;i++)
    {
        cin >> u >> v;
        num[u]++;   num[v]++;
        int f = LCA(u,v);
        num[f]--;   num[FA[f]]--;
    }
    check(1);
    cout << ans;
    return 0;
}