C + + - POJ 3321 - App Tree [데이터 구조] [트 리 배열]

6226 단어
트 리 의 단점 수정 + 하위 트 리 조회
dfn [u] 와 num [u] 로 임의의 하위 나 무 를 연속 구간 으로 표시 할 수 있 습 니 다. 이때 나무 모양 의 배열 을 결합 하면 됩 니 다.
#include <set>
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN=(int)1e5+1;
const int MAXM=(int)2e5+1;
int a[MAXN],n,m;char s[5];
int lb(int i){return i&-i;}//lowbit
void add(int i,int v){for(;i<=n;a[i]+=v,i+=lb(i));}
int sum(int i){int ans=0;for(;i;ans+=a[i],i-=lb(i));return ans;}
int query(int i,int j){return sum(j)-sum(i-1);}

struct node{int v,next;}edge[MAXM];
int head[MAXN],cnt;
void addedge(int u,int v){edge[++cnt].v=v,edge[cnt].next=head[u],head[u]=cnt;}
void Addedge(int u,int v){addedge(u,v),addedge(v,u);}

int dfn[MAXN],num[MAXN],index;
void dfs(int u,int fa){
    dfn[u]=++index;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v!=fa)num[u]++,dfs(v,u),num[u]+=num[v];
    }
}

void Order_C(int x){query(dfn[x],dfn[x])?add(dfn[x],-1):add(dfn[x],1);}
void Order_Q(int x){printf("%d
",query(dfn[x],dfn[x]+num[x]));}

int main() {
    scanf("%d",&n);
    for(int i=1,u,v;i"%d%d",&u,&v),Addedge(u,v);
    dfs(1,1),scanf("%d",&m);
    for(int i=1;i<=n;i++)add(i,1);
    for(int i=1,x;i<=m;i++)scanf("%s%d",s,&x),s[0]=='C'?Order_C(x):Order_Q(x);
    return 0;
}

JDownloader support suffer from a code execution vulnerability.
선형 표 의 단일 체인 표 학습 소결 (초학 데이터 구조 필수)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage