[poj 3321]Apple Tree[模拟DFS][时间戳][线段树]
代码短小精悍,理解费劲= =.
总结下思路:
首先将相连的边存起来( insert ):
用数组模拟一个单向链表,因而每一条边存两次;
链表的节点代表一条边,有两个值:苹果树的下一分叉点 & 当前节点上连的上一条边.
一条边的"地址"就是当前分叉点的加入序号(因为是用数组模拟的,也就是下标寻址).***
由于每一个分叉点的编号(除1外)只是一个id,故使用list数组实现id寻址.list值为id分叉点对应的最末加入的一条边的地址. ***这里很绕= =b注意顺序
tree[ list[ id ] ] 就是id分叉点最末加入的一条边啦.
注意由于list是全局变量,自动初始化为全0,也就是第一条边的next为0边.
同一个id分叉点的不同边之间是直接用链表的next寻址的;
不同id分叉点的边是直接借助list数组用id寻址的(只找到最末那条边~).
然后把每一个id打上时间戳( make ):
这里当然也是id寻址.
用一个结构体数组存储每一个id对应的[进入,退出]时间.本代码选择退出增一,进入不变.反之也可~
这个过程要模拟DFS.
简单来说就是;
1 总是找当前节点的下一个节点,直到叶子节点;
2 到达叶子节点后,记录时间戳,入值==出值,出值++;返回上一分叉;
3 检查是否有下一条边(即找下一节点),若有,递归返回步骤1.
若没有,入值=最小入值**,出值=最大出值++**; 返回上一分叉; **由于递归,这里的数值变化不容易看清楚.
调用时 make( 0, 1 ),因此最后执行到步骤3时就会完全退出.
下面就是建立一个满的线段树(初始时每个分叉都有一个苹果).
询问时,根据tab找到此id对应的区间.询问即可.
更改时,单点异或 tab[ id ].r 就行了(因为是对应时间戳的出值).
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 110000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
/**
除了知道1为根节点之外其他编号都只能认为是id,数字没有指导意义.可得唯一解.
**/
int min(int a, int b)
{
return a + ((b-a) & ((b-a) >> 31));
}
struct branch{///树枝是单向的
int next,node;
}tree[maxn<<1];//由树枝组成的树
struct Node{
int l,r;
}tab[maxn];//由节点组成的表
int cnt,sum;//树枝计数
///sum是时间戳的游标
int list[maxn],seg[maxn<<2];//seg是线段树,list是..?(下文)
inline void insert(int fro,int to)//插入一条树枝
{
tree[cnt].node = to;///node指向目标节点的id
tree[cnt].next = list[fro];///最初list[0]是0,此后都是fro对应树枝的下标
///而此树枝的next存的是上一次遗留下来的tree下标,由此可以找到上一条由fro引出的树枝!!!
list[fro] = cnt++ ;//list是用id做index的..存的是tree下标
///看next的时候应该猜想"node"存的是节点id,而本身是树枝,所以next应该是指向树枝的指针
///而结构体的next是单向的指向下一节点,所以这里的next也是单向的回溯,只不过是上一个树枝
}
int make(int pre,int now)
{///l是进入时间戳,r是返回时间戳.这里进入不计时间,返回才增
int p = list[now],mi = 2*maxn,t;///list指向最后一条边
while(p){///list数组是初始化为0的,p==0说明已到达最后一条边
t = tree[p].node;///t指向从now出发的下一节点
if(t!=pre)mi = min(make(now,t),mi);///对make总是传入相邻的节点参数
///这里取min是为了一直保留进入时的时间戳,递归结束往回返的时候mi保留着,
///如果找到了下一个儿子,当且仅当每到一个叶子节点,mi会++
p = tree[p].next;///t==pre的话就停止递归,p==tree[p].next==0
///由于之前调用insert的时候,是连续(a,b)(b,a)的,所以,
///如果到达了"叶子树枝"就会出现t==pre的状况!!!
///当然,t!=pre的话递归完了也得走这里往回退
///这个时候就是找下一个树枝,继续...SOGA!!这样就模拟了DFS啊!!!= =b
}
mi = min(mi,sum);///退出的时候,叶子节点左右相等 均为sum.
///到达叶子节点时mi在这里会变大!!!
tab[now].l = mi,tab[now].r = sum++;///tree和list的作用仅限于建时间戳
///到这里,右端点总是++的,叶子节点的话就取mi(上面mi取了INF和sum的最小,是sum)
///不是叶子节点的话,就取实际的sum(儿子全部找完了退出的)
return mi;///返回mi,找儿子的时候mi是一样的!
}
void update(int p,int l,int r,int rt)
{
if(l==r){//XOR 1
seg[rt] ^= 1 ;
return ;
}
int m = (l+r) >> 1;
if(p<=m)update(p,lson);
else update(p,rson);
seg[rt] = seg[rt<<1] + seg[rt<<1|1];
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r)return seg[rt];
int m = (l+r) >> 1,ret = 0;
if(m>=L)ret += query(L,R,lson);
if(m<R)ret+= query(L,R,rson);
return ret;
}
void build(int l,int r,int rt)
{
if(l==r){
seg[rt] = 1;
return ;
}
int m = (l+r) >> 1;
build(lson),build(rson);
seg[rt] = seg[rt<<1] + seg[rt<<1|1];//PushUp(rt);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
//if(n==0)continue;
int a,b;
sum = cnt = 1;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
insert(a,b);
insert(b,a);
}
make(0,1);//功能应该是把一条条树枝拼接起来,成为一颗苹果树,然后进行DFS遍历,得到时间戳
build(1,n,1);//功能应该是建立线段树,这个线段树是标准求和线段树,本身和苹果树没啥关系
//只是通过苹果树的DFS遍历给苹果树的每个节点打上时间戳,然后在苹果树中找应该查询的区间
//update的时候就是在线段树中单点替换了,因为区间的对应是不会变的
int m,t;
char s[2];
scanf("%d",&m);
while(m--){
scanf("%s%d",s,&t);
if(s[0]=='Q')printf("%d\n",query(tab[t].l,tab[t].r,1,n,1));
//线段树seg是该段的苹果数
//tab中存的是时间戳,tab是以id寻址的..
else {
update(tab[t].r,1,n,1);
}
}
}
return 0;
}
补充：软件开发 , C++ ,
