[BZOJ] 4196 [Noi 2015] 패키지 관리자
9807 단어 나무.트 리 데이터 구조나무토막
#include
#include
using namespace std;
const int MAXN=1000005;
int n,m;
#define ls (cur<<1)
#define rs ((cur<<1)+1)
#define mid ((l+r)>>1)
int sum[MAXN],lazy[MAXN];
void pushup(int cur){sum[cur]=sum[ls]+sum[rs];}
void pushdown(int cur,int l,int r){
sum[ls]=(lazy[cur])*(mid-l+1);
sum[rs]=(lazy[cur])*(r-mid);
lazy[ls]=lazy[rs]=lazy[cur];
lazy[cur]=-1;
}
void build(int cur,int l,int r){
if(l==r){sum[cur]=0;return;}
build(ls,l,mid);build(rs,mid+1,r);
lazy[cur]=-1;
pushup(cur);
}
void updata(int L,int R,int cur,int l,int r,int w){
if(L<=l&&r<=R){sum[cur]=w*(r-l+1);lazy[cur]=w;return;}
if(lazy[cur]!=-1) pushdown(cur,l,r);
if(L<=mid) updata(L,R,ls,l,mid,w);
if(mid 1,r,w);
pushup(cur);
}
int query(int L,int R,int cur,int l,int r){
if(L<=l&&r<=R) return sum[cur];
if(lazy[cur]!=-1) pushdown(cur,l,r);
int ret=0;
if(L<=mid) ret+=query(L,R,ls,l,mid);
if(mid 1,r);
return ret;
}
int query0(int L,int R,int cur,int l,int r){
if(L<=l&&r<=R) return r-l+1-sum[cur];
if(lazy[cur]!=-1) pushdown(cur,l,r);
int ret=0;
if(L<=mid) ret+=query0(L,R,ls,l,mid);
if(mid 1,r);
return ret;
}
struct Edge{
int next,to;
}e[MAXN<<1];
int ecnt,head[MAXN];
inline void add(int x,int y){
e[++ecnt].to = y;
e[ecnt].next = head[x];
head[x] = ecnt;
}
int dep[MAXN],fa[MAXN],hs[MAXN],siz[MAXN];
void dfs1(int cur,int pre){
fa[cur]=pre;dep[cur]=dep[pre]+1;siz[cur]=1;
int mx=-1;
for(int i=head[cur];i;i=e[i].next){
int v=e[i].to;
if(v==pre) continue;
dfs1(v,cur);
siz[cur]+=siz[v];
if(siz[v]>mx) mx=siz[v],hs[cur]=v;
}
}
int top[MAXN],id[MAXN],cnt;
void dfs2(int cur,int tp){
id[cur]=++cnt;top[cur]=tp;
if(hs[cur]) dfs2(hs[cur],tp);
for(int i=head[cur];i;i=e[i].next){
int v=e[i].to;
if(v==fa[cur]||v==hs[cur]) continue;
dfs2(v,v);
}
}
int query_link(int x,int y){
int ret=0;
while(top[x]!=top[y]){
if(dep[top[x]]id[top[x]],id[x],1,1,n);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ret+=query0(id[x],id[y],1,1,n);
return ret;
}
void updata_link(int x,int y,int w){
while(top[x]!=top[y]){
if(dep[top[x]]id[top[x]],id[x],1,1,n,w);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
updata(id[x],id[y],1,1,n,w);
}
int query_subtree(int x){
return query(id[x],id[x]+siz[x]-1,1,1,n);
}
void updata_subtree(int x,int w){
updata(id[x],id[x]+siz[x]-1,1,1,n,w);
}
int main(){
scanf("%d",&n);
int x;
for(int i=2;i<=n;i++) {
scanf("%d",&x);
x++;
add(i,x);add(x,i);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
scanf("%d",&m);
char s[500];
for(int i=1;i<=m;i++){
scanf("%s%d",s,&x);
x++;
if(s[0]=='i'){
printf("%d
",query_link(1,x));
updata_link(1,x,1);
}else{
printf("%d
",query_subtree(x));
updata_subtree(x,0);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
예제 1.15 UVALive-3902 트리의 검색컨베이어 도어 제목 대의: n대의 기계는 하나의 트리 네트워크로 연결되어 잎 노드는 클라이언트이고 다른 노드는 서버이다. 처음에는 한 대의 서버만 하나의 서비스를 제공했지만 k의 거리 내의 클라이언트만 덮어쓸 수 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.