BZOJ-1103:|BZOJ-1103: [POI2007]大都市meg 题解
题目：****http://www.lydsy.com/JudgeOnline/problem.php?id=1103
先将该树处理成DFS序列，然后用树状数组维护，在首次进入的点出+1，最后退出的点处-1，然后查询时该点的前缀和-1即为答案。每次该边时就将对应的点进入和退出两个位置改成0就好了。总体的说，这是一道有思考性的树状数组题目。
【BZOJ-1103:|BZOJ-1103: [POI2007]大都市meg 题解】代码：
#include #include #include #include #include using namespace std;
#define MAXN 250001#define lowbit(x)(((~(x))+1)&x)int n,m;
struct edge {int t;
edge *next;
edge (){next=NULL;
}} *head[MAXN];
int dfs[MAXN*2];
int first[MAXN],last[MAXN];
int t[MAXN*2];
int IN[MAXN];
void INSERT(int s,int t){edge *p=new(edge);
p->t=t;
p->next=head[s];
head[s]=p;
p=new(edge);
p->t=s;
p->next=head[t];
head[t]=p;
}struct node {int v;
edge *p;
bool flag;
node (int _v,edge *_p,bool _flag):v(_v),p(_p),flag(_flag){}};
stacks;
int N=0;
bool flag[MAXN];
void DFS(){memset(flag,true,sizeof(flag));
while (!s.empty()){s.pop();
}s.push(node(1,head[1],true));
while (!s.empty()){node i=s.top();
flag[i.v]=false;
s.pop();
if (i.flag){dfs[++N]=i.v;
first[i.v]=N;
i.flag=false;
}if (i.p==NULL){dfs[++N]=i.v;
last[i.v]=N;
} else {s.push(node(i.v,i.p->next,false));
if (!flag[i.p->t]){continue;
}IN[i.p->t]=i.v;
s.push(node(i.p->t,head[i.p->t],true));
}}}void Add(int x,int y){while (x<=N) t[x]+=y,x+=lowbit(x);
}int Suffsum(int x){int rec=0;
while (x) rec+=t[x],x-=lowbit(x);
return rec;
}int main(){scanf("%d",&n);
for (int i=0;
i++ 推荐阅读
- 拥有双重称号的超级战神怀着一颗纯洁的心来到了大都市!
- 锦州的公交车票价2元起步，比肩国际大都市还是罔顾民情（）
- 回不去的小县城|回不去的小县城 待不住的大都市
- 糖匠
- 你在哪（）
- 鲈肥菰脆调羹美
- 毕业三年后，你愿意从一线大都市回归三四线的老家工作生活么（）