首页 > 代码库 > 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 大都市