首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。