[JLOI2014] 松鼠的新家（重链剖分+线段树）

题目传送门https://www.luogu.com.cn/problem/P3258好好的一道紫题为什么降绿了……

解题思路

可以先重链剖分一遍，给每个点编上一个号。

然后将树上问题转化为序列问题，那么再次想到线段树。

对于修改  间的路径，我们可以这样操作：

将  跳到同一条重链上，在跳的过程中，逐次对每个重链进行区间操作。

思路比较简单，但代码有点小长……

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,rt,mod;
int a[300001];
vector<int> g[300001];
int dep[300001];
int fa[300001];
int siz[300001];
int son[300001];
int id[300001],top[300001],cnt;
void dfs1(int x,int father,int deep)
{
dep[x]=deep;
fa[x]=father;
siz[x]=1;
int mxson=-1;
for(auto y:g[x])
{
if(y==father)continue;
dfs1(y,x,deep+1);
siz[x]+=siz[y];
if(siz[y]>mxson)
{
mxson=siz[y];
son[x]=y;
}
}
}
void dfs2(int x,int tf)
{
id[x]=++cnt;
top[x]=tf;
if(!son[x])return;
dfs2(son[x],tf);
for(auto y:g[x])
{
if(y==fa[x]||y==son[x])continue;
dfs2(y,y);
}
}
struct tree{
int sum,l,r,add;
}tr[4000001];
void build(int u,int l,int r)
{
tr[u]={0,l,r,0};
if(l==r)
{
tr[u].sum=0;
return;
}
int mid=l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
void push_down(int u)
{
if(tr[u].add)
{
tr[u*2].sum+=(tr[u*2].r-tr[u*2].l+1)*tr[u].add;
tr[u*2].add+=tr[u].add;
tr[u*2+1].sum+=(tr[u*2+1].r-tr[u*2+1].l+1)*tr[u].add;
tr[u*2+1].add+=tr[u].add;
tr[u].add=0;
}
}
void push_up(int u)
{
tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
void change(int u,int l,int r,int d)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
tr[u].sum+=(tr[u].r-tr[u].l+1)*d;
tr[u].add+=d;
return;
}
push_down(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)
change(u*2,l,r,d);
if(r>mid)
change(u*2+1,l,r,d);
push_up(u);
}
int query(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
return tr[u].sum;
}
push_down(u);
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid)
res+=query(u*2,l,r);
if(r>mid)
res+=query(u*2+1,l,r);
return res;
}
void update(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
change(1,id[top[x]],id[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
change(1,id[x],id[y],1);

}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}

int u,v;
for(int i=1;i<n;i++)
{
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
for(int i=1;i<n;i++)
{
update(a[i],a[i+1]);
change(1,id[a[i+1]],id[a[i+1]],-1);
}

for(int i=1;i<=n;i++)
{
cout<<query(1,id[i],id[i])<<"\n";
}
}

原文地址：https://blog.csdn.net/2403_87021226/article/details/143989083

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！