题解 P3258 【[JLOI2014]松鼠的新家】

· · 题解

这是树剖的模板题了吧……

题目要求我们维护一棵树,进行路径修改和单点查询。

如果不会树链剖分的话请点这里

考虑实现方法:

首先,我们想到直接对每条路径上的每一个点加一就可以了,最后一个点-1,这样好像就算做出来了。

但是!我们仔细想想可以发现,每一个路径的终点又是下条路径的起点,而我们对其修改了两遍,所以这个算法就有问题了

博主想到了两种解题方法

1、对每条路径修改后,将终点的值减一:这样的话,就不存在重复覆盖的问题了,而且这也恰好符合了终点要-1的情况。

代码如下:

#include<bits/stdc++.h>
using namespace std;
long long max1,n,m,r1,p,q,x,y,k,i,c[4000001],siz[1000001],id[1000001],son[1000001],l[4000001],r[4000001],a[1000001],w[1000001],cnt,z[4000001],he[1000001],ne[2000001],to[2000001],top[1000001],d[1000001],f[1000001];
void did1(long long u,long long fat,long long deep)
{
    d[u]=deep;
    f[u]=fat;
    siz[u]=1;
    for (long long i=he[u];i;i=ne[i])
    {
        long long v=to[i];
        if (v==f[u]) continue;
        did1(v,u,deep+1);
        if (siz[v]>siz[son[u]]) son[u]=v;
        siz[u]+=siz[v];
    }
}
void did2(long long u,long long t)
{
    top[u]=t;
    id[u]=++cnt;
    if (!son[u]) return;
    did2(son[u],t);
    for (long long i=he[u];i;i=ne[i])
    {
        long long v=to[i];
        if (v==f[u]||v==son[u]) continue;
        did2(v,v);
    }
}
void xiafang(long long u)
{
    z[u*2]+=c[u]*(r[u*2]-l[u*2]+1);
    z[u*2+1]+=c[u]*(r[u*2+1]-l[u*2+1]+1);
    c[u*2]+=c[u];
    c[u*2+1]+=c[u];
    c[u]=0;
}
void build(long long u,long long l1,long long r1)
{
    l[u]=l1;
    r[u]=r1;
    if (l1==r1)
        return;
    build(u*2,l1,(l1+r1)/2);
    build(u*2+1,(l1+r1)/2+1,r1);
    z[u]=(z[u*2]+z[u*2+1]);
}
void jia(long long u,long long l1,long long r1,long long k)
{
    if (l[u]>r1||r[u]<l1) return;
    if (l[u]>=l1&&r[u]<=r1)
    {
        z[u]=(z[u]+k*(r[u]-l[u]+1));
        c[u]+=k;
        return;
    }
    xiafang(u);
    jia(u*2,l1,r1,k);
    jia(u*2+1,l1,r1,k);
    z[u]=(z[u*2]+z[u*2+1]);
}
long long qui(long long u,long long l1,long long r1)
{
    if (l[u]>r1||r[u]<l1) return 0;
    if (l[u]>=l1&&r[u]<=r1) return z[u];
    xiafang(u);
    return (qui(u*2,l1,r1)+qui(u*2+1,l1,r1));
}
void jiapro(long long x,long long y,long long k)
{
    while(top[x]!=top[y])
    {
        if (d[top[x]]<d[top[y]]) swap(x,y);
        jia(1,id[top[x]],id[x],k);
        x=f[top[x]];
    }
    if (d[x]>d[y]) swap(x,y);
    jia(1,id[x],id[y],k); 
}
long long quipro(long long x,long long y)
{
    long long ans=0;
    while(top[x]!=top[y])
    {
        if (d[top[x]]<d[top[y]]) swap(x,y);
        ans=(ans+qui(1,id[top[x]],id[x]));
        x=f[top[x]];
    }
    if (d[x]>d[y]) swap(x,y);
    ans=(ans+qui(1,id[x],id[y]));
    return ans;
}
void jiason(long long x,long long k)
{
    jia(1,id[x],id[x]+siz[x]-1,k);
}
long long quison(long long x)
{
    return qui(1,id[x],id[x]+siz[x]-1);
}
int main()
{
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for (i=1;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        cnt++;
        ne[cnt]=he[x];
        to[cnt]=y;
        he[x]=cnt;
        cnt++;
        ne[cnt]=he[y];
        to[cnt]=x;
        he[y]=cnt;
    }
    cnt=0;
    did1(1,0,1);
    did2(1,1);
    build(1,1,n);
    for (i=1;i<n;i++)
    {
        jiapro(a[i],a[i+1],1);
        jiapro(a[i+1],a[i+1],-1);//将终点的值-1
    }
    for (i=1;i<=n;i++)
        printf("%lld\n",qui(1,id[i],id[i]));//直接求出每个点的糖果数
    return 0;
}

这是能AC的。

2、将除一号点以外的所有点权-1。

原理证明:除一号点、终点以外的所有点都被当成了路径终点1次、起点1次,而终点本因-1,所以也是正确的(但博主没试过,代码写好了没交)

#include<bits/stdc++.h>
using namespace std;
long long max1,n,m,r1,p,q,x,y,k,i,c[4000001],siz[1000001],id[1000001],son[1000001],l[4000001],r[4000001],a[1000001],w[1000001],cnt,z[4000001],he[1000001],ne[2000001],to[2000001],top[1000001],d[1000001],f[1000001];
void did1(long long u,long long fat,long long deep)
{
    d[u]=deep;
    f[u]=fat;
    siz[u]=1;
    for (long long i=he[u];i;i=ne[i])
    {
        long long v=to[i];
        if (v==f[u]) continue;
        did1(v,u,deep+1);
        if (siz[v]>siz[son[u]]) son[u]=v;
        siz[u]+=siz[v];
    }
}
void did2(long long u,long long t)
{
    top[u]=t;
    id[u]=++cnt;
    if (!son[u]) return;
    did2(son[u],t);
    for (long long i=he[u];i;i=ne[i])
    {
        long long v=to[i];
        if (v==f[u]||v==son[u]) continue;
        did2(v,v);
    }
}
void xiafang(long long u)
{
    z[u*2]+=c[u]*(r[u*2]-l[u*2]+1);
    z[u*2+1]+=c[u]*(r[u*2+1]-l[u*2+1]+1);
    c[u*2]+=c[u];
    c[u*2+1]+=c[u];
    c[u]=0;
}
void build(long long u,long long l1,long long r1)
{
    l[u]=l1;
    r[u]=r1;
    if (l1==r1)
        return;
    build(u*2,l1,(l1+r1)/2);
    build(u*2+1,(l1+r1)/2+1,r1);
    z[u]=(z[u*2]+z[u*2+1]);
}
void jia(long long u,long long l1,long long r1,long long k)
{
    if (l[u]>r1||r[u]<l1) return;
    if (l[u]>=l1&&r[u]<=r1)
    {
        z[u]=(z[u]+k*(r[u]-l[u]+1));
        c[u]+=k;
        return;
    }
    xiafang(u);
    jia(u*2,l1,r1,k);
    jia(u*2+1,l1,r1,k);
    z[u]=(z[u*2]+z[u*2+1]);
}
long long qui(long long u,long long l1,long long r1)
{
    if (l[u]>r1||r[u]<l1) return 0;
    if (l[u]>=l1&&r[u]<=r1) return z[u];
    xiafang(u);
    return (qui(u*2,l1,r1)+qui(u*2+1,l1,r1));
}
void jiapro(long long x,long long y,long long k)
{
    while(top[x]!=top[y])
    {
        if (d[top[x]]<d[top[y]]) swap(x,y);
        jia(1,id[top[x]],id[x],k);
        x=f[top[x]];
    }
    if (d[x]>d[y]) swap(x,y);
    jia(1,id[x],id[y],k); 
}
long long quipro(long long x,long long y)
{
    long long ans=0;
    while(top[x]!=top[y])
    {
        if (d[top[x]]<d[top[y]]) swap(x,y);
        ans=(ans+qui(1,id[top[x]],id[x]));
        x=f[top[x]];
    }
    if (d[x]>d[y]) swap(x,y);
    ans=(ans+qui(1,id[x],id[y]));
    return ans;
}
void jiason(long long x,long long k)
{
    jia(1,id[x],id[x]+siz[x]-1,k);
}
long long quison(long long x)
{
    return qui(1,id[x],id[x]+siz[x]-1);
}
int main()
{
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for (i=1;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        cnt++;
        ne[cnt]=he[x];
        to[cnt]=y;
        he[x]=cnt;
        cnt++;
        ne[cnt]=he[y];
        to[cnt]=x;
        he[y]=cnt;
    }
    cnt=0;
    did1(1,0,1);
    did2(1,1);
    build(1,1,n);
    for (i=1;i<n;i++)
        jiapro(a[i],a[i+1],1);
    printf("%lld\n",qui(1,id[1],id[1]));
    for (i=2;i<=n;i++)
        printf("%lld\n",qui(1,id[i],id[i])-1);
    return 0;
}

没试过,也许是对的?也许哪里写出锅了?不过思想应该是对的,上面的代码不保证正确,如果有兴趣的同学可以自己尝试用我那个算法试试。

调慢了时间复杂度,复制代码无法AC(当然你优化我也不拦你)