[BZOJ 4196] [NOI 2015] 패키지 관리자 (트 리 체인 분할)
대체적으로 n n 개의 소프트웨어 패키지 가 있 는데 그들의 의존 관 계 는 나무 한 그루 를 형성한다.지금 패 키 지 를 설치 하거나 마 운 트 해제 하면 몇 개의 패 키 지 를 설치 하 는 상태 에 영향 을 줄 수 있 는 지 물 어보 세 요.
나무 사슬 분할
이 문 제 는 트 리 체인 분할 알고리즘 이 비교적 입문 한 문제 일 것 이다.
L i n k Link Link
트 리 체인 분할 상세 참조 블 로그 트 리 체인 분할 학습 노트
설치 작업
우 리 는 설치 와 마 운 트 해제 두 가지 작업 을 각각 처리 합 니 다.
우선 설치 작업 이 어떻게 이 루어 져 야 하 는 지 살 펴 보 자.
패 키 지 를 설치 하려 면 의존 하 는 패 키 지 를 0 0 호 패키지 까지 모두 설치 해 야 한다.
제목 에서 제 시 된 관 계 를 나무 로 본다 면 이 패 키 지 를 0 0 번 노드 (즉 루트 노드) 의 경로 에 있 는 모든 패 키 지 를 설치 하 는 것 이다.
나무 사슬 로 나 누 면 쉽게 할 수 있 을 거 예요.
마 운 트 해제 작업
마 운 트 해제 작업 을 어떻게 실현 하 는 지 다시 한번 봅 시다.
패 키 지 를 지 우 는 것 을 고려 하면 모든 의존 하 는 패 키 지 는 모두 마 운 트 해제 되 고, 패 키 지 를 의존 하 는 패 키 지 는 모두 마 운 트 해제 되 는 것 으로 추정 된다.
이 패 키 지 를 뿌리 로 하 는 하위 트 리 안의 모든 패 키 지 를 마 운 트 해제 하 는 셈 이다.
나무 사슬 로 쪼 개 도 쉽게 할 수 있 을 거 예요.
코드
#include
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)
#define abs(x) ((x)<0?-(x):(x))
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define N 100000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,ee=0,lnk[N+5];
struct edge
{
int to,nxt;
}e[2*N+5];
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize
int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];double w;
public:
FIO() {FinNow=FinEnd=Fin;}
inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));x*=f;}
inline void read_char(char &x) {while(isspace(x=tc()));}
inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc()));}
inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
inline void write_char(char x) {pc(x);}
inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
inline void end() {fwrite(Fout,1,FoutSize,stdout);}
}F;
class TreeChainDissection//
{
private:
#define PushUp(x) (Sum[x]=Sum[x<<1]+Sum[x<<1|1])
#define PushDown(x,ln,rn) ((~flag[x]?(flag[x]?(Sum[x<<1]=ln,Sum[x<<1|1]=rn,flag[x<<1]=flag[x<<1|1]=1):(Sum[x<<1]=Sum[x<<1|1]=flag[x<<1]=flag[x<<1|1]=0)):0),flag[x]=-1)
int d,fa[N+5],son[N+5],sz[N+5],Top[N+5],dfn[N+5],fac[N+5],Depth[N+5],Sum[N<<2],flag[N<<2];
inline void dfs1(int x)// dfs
{
register int i;
for(sz[x]=1,i=lnk[x];i;i=e[i].nxt)
{
if(!(fa[x]^e[i].to)) continue;
fa[e[i].to]=x,Depth[e[i].to]=Depth[x]+1,dfs1(e[i].to),sz[x]+=sz[e[i].to];
if(sz[e[i].to]>sz[son[x]]) son[x]=e[i].to;
}
}
inline void dfs2(int x,int col)// dfs
{
register int i;
if(son[fac[dfn[x]=++d]=x]) dfs2(son[x],col);
for(Top[x]=col,i=lnk[x];i;i=e[i].nxt)
{
if(!(fa[x]^e[i].to&&son[x]^e[i].to)) continue;
dfs2(e[i].to,e[i].to);
}
}
inline void Build(int l,int r,int rt)//
{
flag[rt]=-1;
if(l^r)
{
register int mid=l+r>>1;
if(l<=mid) Build(l,mid,rt<<1);
if(r>mid) Build(mid+1,r,rt<<1|1);
}
}
inline int Update(int l,int r,int rt,int ul,int ur,int x)// [ul...ur] x(x=0 ,x=1 ),
{
register int res=0;
if(ul<=l&&r<=ur) {register int t;(x?(t=r-l+1,flag[rt]=1):(t=0,flag[rt]=0)),res=abs(t-Sum[rt]),Sum[rt]=t;return res;}
register int mid=l+r>>1;
PushDown(rt,mid-l+1,r-mid);
if(ul<=mid) res=Update(l,mid,rt<<1,ul,ur,x);
if(ur>mid) res+=Update(mid+1,r,rt<<1|1,ul,ur,x);
PushUp(rt);
return res;
}
public:
inline void Init() {dfs1(1),dfs2(1,1),Build(1,n,1);}
inline int uninstall(int pos) {return Update(1,n,1,dfn[pos],dfn[pos]+sz[pos]-1,0);}// , 0
inline int install(int pos)// , 1
{
register int res=0;
while(Top[pos]>>1) res+=Update(1,n,1,dfn[Top[pos]],dfn[pos],1),pos=fa[Top[pos]];
return res+Update(1,n,1,1,dfn[pos],1);
}
}S;
int main()
{
register int i,Q,x;register char op;
for(F.read(n),i=2;i<=n;++i) F.read(x),add(x+1,i);
for(S.Init(),F.read(Q);Q;--Q)
{
F.read_char(op),F.read(x);
if(op^'u') F.write(S.install(x+1)),F.write_char('
');//
else F.write(S.uninstall(x+1)),F.write_char('
');//
}
return F.end(),0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3930: [CQOI2015] 선택거의 짠 물고기일 거야.. 처음에 제목 yy에 대해 정확할 것 같고 복잡도 계산이 안 되는 검색을 했는데 잘 안 되는 것 같아서 DP를 생각하고 정확해 보이는 DP를 생각해서 끊었어요.그럼 용납하고 싶다......설...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.