首页 > 代码库 > 【POI2007】【Bzoj 1103】大都市meg

【POI2007】【Bzoj 1103】大都市meg

http://www.lydsy.com/JudgeOnline/problem.php?id=1103

在线查询某点到根节点的点权和,参考DFS序&欧拉序列,用树状数组维护即可O(nlogn)

// <meg.cpp> - Sun Oct  2 08:13:38 2016// This file is made by YJinpeng,created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is. #include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>using namespace std;const int MAXN=250010;inline int gi() {    register int w=0,q=0;register char ch=getchar();    while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘)ch=getchar();    if(ch==‘-‘)q=1,ch=getchar();    while(ch>=‘0‘&&ch<=‘9‘)w=w*10+ch-‘0‘,ch=getchar();    return q?-w:w;}int t,n,to[MAXN],ne[MAXN],fr[MAXN],b[MAXN],e[MAXN],c[MAXN];void add(int u,int v){to[++t]=v;ne[t]=fr[u];fr[u]=t;}void dfs(int x){    b[x]=++t;    for(int i=fr[x];i;i=ne[i])dfs(to[i]);    e[x]=t+1;}void plu(int x,int u){    for(;x<=n;x+=(-x)&x)c[x]+=u;}int src(int x){    int ans=0;    for(;x;x-=(-x)&x)ans+=c[x];    return ans;}int main(){    n=gi();    for(int i=1;i<n;i++){        int u=gi(),v=gi();        if(u>v)swap(u,v);        add(u,v);    }    t=0;dfs(1);    for(int i=2;i<=n;i++)        plu(b[i],1),plu(e[i],-1);    int m=gi()+n-1;    while(m--){        char ch=getchar();        while(ch!=‘W‘&&ch!=‘A‘)ch=getchar();        if(ch==‘A‘){            int u=gi(),v=gi();            if(u>v)swap(u,v);            plu(b[v],-1),plu(e[v],1);        }else printf("%d\n",src(b[gi()]));    }    return 0;}

  

【POI2007】【Bzoj 1103】大都市meg