树上差分(CF 191C)

2018-07-25 15:34:41


树上差分有两种(其实也可以说是前缀和):

一种是用来统计一条边被覆盖了多少次。对于树上的一条路径u,v,我们可以把它拆成u->Lca,v->Lca。我们和处理线性的差分一样,让c[u]++,c[Lca]--,c[v]++,c[Lca]--(c为差分数组)。这样就可以表示出u->v这条路径的覆盖次数+1。统计的时候,对于一条边,它被覆盖的次数,就是下端端点这颗子树的c数组值之和。

另一种就是点的差分,也就是求点被覆盖了几次。基本操作相同,只是在处理c数组时,对于路径u->v,我们让c[u]++,c[v]++,c[Lca]--,c[fa[Lca]]--。原因是u->v这条路径覆盖了Lca,而边差分时并没有覆盖Lca作为下端点的边。

对于这道题,自然是边差分模板。。


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,cnt=0;
int head[501000],nxt[501000],to[501000];
int d[501000],f[25][501000],num[501000];
int p[501000];
struct Edge
{
    int x,y;
}e[501000];
void addedge(int x,int y)
{
    cnt++;
    nxt[cnt]=head[x];
    head[x]=cnt;
    to[cnt]=y;
}
void dfs(int u,int dep)
{
    d[u]=dep,p[++cnt]=u;
    for(int i=head[u];i!=-1;i=nxt[i])
    {
        int v=to[i];
        if(!d[v]) f[0][v]=u,dfs(v,dep+1);
    }
}
int Lca(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(d[f[i][x]]>=d[y]) x=f[i][x];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(f[i][x]!=f[i][y])
        {
            x=f[i][x];
            y=f[i][y];
        }
    return f[0][x];
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
        e[i].x=x,e[i].y=y;
    }
    f[0][1]=0;
    cnt=0;
    dfs(1,1);
    for(int i=1;i<=20;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=f[i-1][f[i-1][j]];
    scanf("%d",&k);
    for(int i=1;i<=k;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        num[x]++,num[y]++,num[Lca(x,y)]-=2;
    }
    for(int i=n;i>=1;i--)
        num[f[0][p[i]]]+=num[p[i]];
    for(int i=1;i<n;i++)
    {
        if(d[e[i].x]<d[e[i].y]) e[i].x=e[i].y;//利用深度数组,得到这条边的下端点
        printf("%d ",num[e[i].x]);
    }
    return 0;
}