[ NOI 2015 ] 软件包管理器
题目大意:思路分析：怎么套线段树？怎么算改变状态的数量？
代码总结
题目描述(luogu.org) 题目描述(codevs.cn)
题目大意:
这里有一些软件，下载它，必须先下载它的所有祖先；删除它，必须先删除它的所有儿子。 由于这是树形结构，而且又让进行序列操作，自然想到了树链剖分。数据范围( n<=10^5 ) 树剖可过。
思路分析：
怎么套线段树？
看上去不好套，但是仔细想想：如果用1表示已安装，0表示未安装，那么整个树就是一个零一串。对于安装操作，就是把x点到1号点的数值全部变为1。对于删除操作，就是把它的子树都变为0。
怎么算改变状态的数量？
对于安装操作，先算出x点到1号点的和，这也就是有几个数为一。再用x点的深度，减去这个数值，即为这条路径上0的个数。 对于删除操作，求出这个点子树和，还是这颗子树有一个树为一，即为答案。
具体细节看代码
代码
#include<iostream>
#include<cstdio>
using namespace std
;
#define N 150000
int inp(){
int Ans
=0;bool o
=false;char c
;
while((c
=getchar())<'0'||c
>'9')if(c
=='-')o
=true;Ans
=c
-48;
while((c
=getchar())>='0'&&c
<='9')Ans
=(Ans
<<3)+(Ans
<<1)+c
-48;
return o
==true?-Ans
:Ans
;
}
struct Edge
{int t
,nxt
;}edge
[N
<<1];
int tot
,n
,m
,first
[N
];
int cnt
,deep
[N
],fa
[N
],size
[N
],hson
[N
],top
[N
],id
[N
];
int sum
[N
<<2],add
[N
<<2];
char ch
[20];
void build(int f
,int t
){
edge
[++tot
]=(Edge
){t
,first
[f
]},first
[f
]=tot
,
edge
[++tot
]=(Edge
){f
,first
[t
]},first
[t
]=tot
;
}
void dfs1(int x
,int dad
)
{
fa
[x
]=dad
,deep
[x
]=deep
[dad
]+1,size
[x
]=1;int maxson
=-1;
for(int i
=first
[x
];i
;i
=edge
[i
].nxt
)
{
int t
=edge
[i
].t
;
if(t
==dad
)continue;
dfs1(t
,x
);
if(size
[t
]>maxson
)maxson
=size
[t
],hson
[x
]=t
;
size
[x
]+=size
[t
];
}
}
void dfs2(int x
,int topfa
)
{
id
[x
]=++cnt
,top
[x
]=topfa
;
if(!hson
[x
])return;
dfs2(hson
[x
],topfa
);
for(int i
=first
[x
];i
;i
=edge
[i
].nxt
)
{
int t
=edge
[i
].t
;
if(t
==fa
[x
]||t
==hson
[x
])continue;
dfs2(t
,t
);
}
}
void pushup(int root
){sum
[root
]=sum
[root
<<1]+sum
[root
<<1|1];}
void pushdown(int root
,int ln
,int rn
)
{
if(add
[root
]==1)
{
add
[root
<<1]=add
[root
<<1|1]=1;
sum
[root
<<1]=ln
,sum
[root
<<1|1]=rn
;
add
[root
]=0;
}
if(add
[root
]==2)
{
add
[root
<<1]=add
[root
<<1|1]=2;
sum
[root
<<1]=0,sum
[root
<<1|1]=0;
add
[root
]=0;
}
}
int qsum(int L
,int R
,int l
,int r
,int root
)
{
if(L
>R
)swap(L
,R
);
if(L
<=l
&&r
<=R
){int x
=sum
[root
];sum
[root
]=r
-l
+1,add
[root
]=1;return x
;}
int mid
=(l
+r
)>>1,ans
=0;
pushdown(root
,mid
-l
+1,r
-mid
);
if(L
<=mid
)ans
+=qsum(L
,R
,l
,mid
,root
<<1);
if(R
>mid
)ans
+=qsum(L
,R
,mid
+1,r
,root
<<1|1);
pushup(root
);
return ans
;
}
int Qsum(int L
,int R
,int l
,int r
,int root
)
{
if(L
>R
)swap(L
,R
);
if(L
<=l
&&r
<=R
){int x
=sum
[root
];sum
[root
]=0,add
[root
]=2;return x
;}
int mid
=(l
+r
)>>1,ans
=0;
pushdown(root
,mid
-l
+1,r
-mid
);
if(L
<=mid
)ans
+=Qsum(L
,R
,l
,mid
,root
<<1);
if(R
>mid
)ans
+=Qsum(L
,R
,mid
+1,r
,root
<<1|1);
pushup(root
);
return ans
;
}
int main()
{
n
=inp();
for(int t
,i
=1;i
<n
;i
++)
t
=inp(),build(i
+1,t
+1);
dfs1(1,0),dfs2(1,1);
m
=inp();
for(int i
=1,x
,f
;i
<=m
;i
++)
{
scanf("%s",ch
),f
=x
=inp(),f
++,x
++;
if(ch
[0]=='i')
{
int ans
=0;
while(top
[x
]!=top
[1])
{
ans
+=qsum(id
[x
],id
[top
[x
]],1,n
,1);
x
=fa
[top
[x
]];
}
ans
+=qsum(id
[x
],id
[1],1,n
,1);
cout
<<deep
[f
]-ans
<<endl
;
}
if(ch
[0]=='u')
{
int ans
=Qsum(id
[x
],id
[x
]+size
[x
]-1,1,n
,1);
cout
<<ans
<<endl
;
}
}
}
总结
这个题的思路不难，也没有坑点，算是树剖入门变式题目。
NOIp2018 RP++ ~
