[Codeforces 343D] Water Tree dfs 트리 + 세그먼트 트리
9543 단어 DFScodeforces
제목: 한 그루의 나무에 1, v점과 그 자수에 물을 붓기 2, v점과 v를 뿌리로 가는 경로에서 물을 빼기 3, v점에 물이 있는지 묻기
사고방식: 1.ffs 트리, 처리 가능한 구간;2. 라인 트리 관개(구간 갱신)+lazy 처리;3. 워터프루프 갱신하기;
주의:1.물 조건(push-up);2. 관개 구간에 시간이 있으면---아버지 노드는 반드시 비어있다(판단+단점갱신)!!!
부호를 붙이다
#include<iostream>
#include<vector>
#include<stdio.h>
#define lson (id*2)
#define rson (id*2+1)
using namespace std;
int n;
int in[550000];
int out[550000];
int tree[550000*8];
int pos[550000];
int lazy[550000*8];
int num=0;
vector<int> lin[550000];
bool flag=false;
void dfs(int x,int pre)
{
in[x]=++num;
for(int i=0;i<lin[x].size();i++)
{
int v=lin[x][i];
if(v!=pre)
{
pos[v]=x;
dfs(v,x);
}
}
out[x]=num;
}
void push_down(int id,int l,int mid,int r)
{
if(lazy[id]==0) return ;
tree[lson]=tree[rson]=lazy[lson]=lazy[rson]=1;
lazy[id]=0;
}
void push_up(int id)
{
if(tree[lson]+tree[rson]==2) tree[id]=1;
else tree[id]=0;
}
void add(int id,int l,int r,int L,int R,int V)
{
if(l==0) return ;
if(l>R||r<L) return ;
if(l>=L&&r<=R)
{
if(tree[id]==0) flag=1;
tree[id]=V;
if(V==1) lazy[id]=V;
return ;
}
int mid=(l+r)/2;
push_down(id,l,mid,r);
add(lson,l,mid,L,R,V);
add(rson,mid+1,r,L,R,V);
push_up(id);
}
void query(int id,int l,int r,int L,int R)
{
if(l>R||r<L) return ;
if(l>=L&&r<=R)
{
if(tree[id]==0) flag=1;
return ;
}
int mid=(l+r)>>1;
push_down(id,l,mid,l);
query(lson,l,mid,L,R);
query(rson,mid+1,r,L,R);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int aa,bb;
scanf("%d%d",&aa,&bb);
lin[aa].push_back(bb);
lin[bb].push_back(aa);
}
pos[1]=0;
dfs(1,0);
int Q;
scanf("%d",&Q);
for(int i=1;i<=Q;i++)
{
int aa,bb;
scanf("%d%d",&aa,&bb);
if(aa==1)
{
flag=false;//2. ———— !
add(1,1,n,in[bb],out[bb],1);
if(flag==true)
{
add(1,1,n,in[pos[bb]],in[pos[bb]],0);
}
}
else
if(aa==2)
{
add(1,1,n,in[bb],in[bb],0);
}
if(aa==3)
{
flag=false;
query(1,1,n,in[bb],out[bb]);
if(flag==true) printf("0
");
else printf("1
");
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ] 5568 카드 놓기아이디어 Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고 sb에 고른 카드를 담도록 하였다. 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.