首页 > 代码库 > BZOJ 1103 大都市
BZOJ 1103 大都市
dfs序+BIT。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxv 250050#define maxe 500500using namespace std;int n,x,y,m,g[maxv],nume=0,w[maxv],mx[maxv],dis[maxv],val[maxv],fath[maxv],times=0;char s[5];struct edge{ int v,nxt;}e[maxe];int lowbit(int x){ return (x&(-x));}void addedge(int u,int v){ e[++nume].v=v; e[nume].nxt=g[u]; g[u]=nume;}void dfs(int x){ w[x]=mx[x]=++times; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=fath[x]) { dis[v]=dis[x]+1;fath[v]=x; dfs(v); mx[x]=max(mx[x],mx[v]); } }}void add(int pos,int x){ for (int i=pos;i<=n+1;i+=lowbit(i)) val[i]+=x;}void modify(){ scanf("%d%d",&x,&y); if (dis[x]>dis[y]) swap(x,y); add(w[y],1);add(mx[y]+1,-1);}void ask(){ scanf("%d",&x);int regis=x;x=w[x]; int ret=0; while (x) { ret+=val[x]; x-=lowbit(x); } printf("%d\n",dis[regis]-ret);}int main(){ scanf("%d",&n); for (int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); addedge(x,y);addedge(y,x); } dfs(1); scanf("%d",&m); for (int i=1;i<=n+m-1;i++) { scanf("%s",s); if (s[0]==‘A‘) modify(); else ask(); } return 0;}
BZOJ 1103 大都市
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。