题解 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(当然你优化我也不拦你)